## Sunday, July 30, 2017

Implement 28 - Implement strStr()
http://wxx5433.github.io/replace.html
function replace(string orig, string find, string repl)
-- replaces every instances of string find with string repl
-- returned the modified string
1. After one replacing, if the suffix of replaced string is the prefix of the find string, should we replace again? For instance, replace("babcc", "abc", "cab"). We first change it to "bcabc", should we change it to "bccab" or not?

### Analysis

We need to first count how many times the pattern have appeared in the original string. Otherwise, we need to copy the char array many times each time we replace a string. (Since len(find) can be different from len(repl)).

### Complexity

Time: Suppose len(orig) = m, len(find) = n, then we need O(mn) time to count and O(m + count*n) time to replace.
Space: O(m), we need extra space to store the start index of a found pattern in the original string.
```    public static String replace(String orig, String find, String repl) {
List<Integer> index = findPattern(orig, find);
int count = index.size();
// compute length after replacement
int newLen = orig.length() + count * (repl.length() - find.length());
char[] result = new char[newLen];
// replace
int i = 0, k = 0;
int resultIndex = 0;
while( i < orig.length()) {
if (k < count && i == index.get(k)) {
for (int j = 0; j < repl.length(); ++j) {
result[resultIndex++] = repl.charAt(j);
}
++k;
i += find.length();
} else {
result[resultIndex++] = orig.charAt(i++);
}
}
return new String(result);
}

/**
* find how many times the pattern string have appeared in the orig string
* @param orig original string
* @param find pattern string to find
* @return a list of the start index of a fuond pattern in the original string
*/
private static List<Integer> findPattern(String orig, String find) {
List<Integer> index = new ArrayList<Integer>();
int i = 0, j = 0;
// count how many times "find" have appeared
while (i + find.length() <= orig.length()) {
int k = i;
j = 0;
while (j < find.length()) {
if (orig.charAt(k) != find.charAt(j)) {
break;
}
++k;
++j;
}
if (j == find.length()) {
i += find.length();
} else {
++i;
}
}
return index;
}```

## Labels

LeetCode (1200) GeeksforGeeks (1127) Review (894) Algorithm (795) LeetCode - Review (649) to-do (639) Dynamic Programming (330) Classic Algorithm (323) Classic Interview (288) Google Interview (245) Tree (145) POJ (140) Difficult Algorithm (131) LeetCode - Phone (127) EPI (125) Bit Algorithms (121) Different Solutions (120) Lintcode (112) Math (109) Smart Algorithm (109) HackerRank (89) Binary Search (84) Binary Tree (82) Greedy Algorithm (80) Graph Algorithm (76) DFS (73) Stack (68) Interview Corner (61) List (58) BFS (57) Codility (54) ComProGuide (52) LeetCode Hard (52) Trie (49) Interval (46) USACO (46) ACM-ICPC (41) Segment Tree (41) Union-Find (41) Data Structure (40) Knapsack (40) Matrix (40) Jobdu (39) Backtracking (38) String Algorithm (38) TopCoder (38) Codeforces (36) Must Known (36) Sort (35) Sliding Window (34) Array (33) prismoskills (33) Priority Queue (32) HDU (31) Google Code Jam (30) LeetCode - DP (30) Permutation (30) Puzzles (30) Array O(N) (29) Company-Airbnb (29) Company-Zenefits (28) Graph (28) Palindrome (28) to-do-must (28) Random (27) Queue (26) Time Complexity (26) GeeksQuiz (25) Logic Thinking (25) Pre-Sort (25) hihocoder (25) Company-Facebook (23) High Frequency (23) Two Pointers (23) Algorithm Game (22) Bisection Method (22) Follow Up (22) Hash (22) DFS + Review (21) Brain Teaser (20) CareerCup (20) Merge Sort (20) O(N) (20) Ordered Stack (20) Topological Sort (19) UVA (19) Company-Uber (17) Game Theory (17) Probabilities (17) Codercareer (16) DP - Tree (16) Heap (16) Iterator (16) Shortest Path (16) String Search (16) Tree Traversal (16) itint5 (16) Difficult (15) BST (14) KMP (14) LeetCode - DFS (14) Number (14) Number Theory (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Euclidean GCD (13) Majority (13) Reverse Thinking (13) mitbbs (13) Bisection (12) Combination (12) Modify Tree (12) Proof (12) Reconstruct Tree (12) TreeMap (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Graph DFS (11) LCA (11) Miscs (11) O(1) Space (11) Prefix Sum (11) Princeton (11) Rolling Hash (11) X Sum (11) 挑战程序设计竞赛 (11) Bucket Sort (10) Coin Change (10) DFS+Cache (10) DP - Bit Masking (10) DP - Digit (10) DP - Interval (10) HackerRank Easy (10) MinMax (10) SPOJ (10) Simulation (10) Theory (10) Tutorialhorizon (10) Mathblog (9) Max-Min Flow (9) Quick Sort (9) Stock (9) Use XOR (9) Book Notes (8) Bottom-Up (8) DFS+BFS (8) Linked List (8) Prime (8) Suffix Tree (8) Tech-Queries (8) TreeSet (8) 穷竭搜索 (8) Expression (7) Game Nim (7) Graph BFS (7) Hackerearth (7) Inversion (7) Quick Select (7) Radix Sort (7) Tree DP (7) n00tc0d3r (7) 蓝桥杯 (7) DFS+DP (6) Dijkstra (6) Dutch Flag (6) How To (6) Manacher (6) One Pass (6) Pruning (6) Rabin-Karp (6) Sampling (6) Schedule (6) Stream (6) Suffix Array (6) Sweep Line (6) Threaded (6) Xpost (6) reddit (6) AI (5) Big Data (5) Brute Force (5) Code Kata (5) Coding (5) Convex Hull (5) Crazyforcode (5) Cycle (5) Find Rule (5) Flood fill (5) Graph Cycle (5) Immutability (5) Java (5) Maze (5) Pre-Sum (5) Quadtrees (5) Quora (5) Subarray Sum (5) Sudoku (5) Word Search (5) jiuzhang (5) 单调栈 (5) 1point3acres (4) Abbreviation (4) Anagram (4) Anagrams (4) Chess Game (4) Dequeue (4) Distributed (4) Histogram (4) MST (4) N Queens (4) Probability (4) Programcreek (4) Subset Sum (4) Subsets (4) Symbol Table (4) Triangle (4) Water Jug (4) algnotes (4) fgdsb (4) to-do-2 (4) 最大化最小值 (4) 树形DP (4) A Star (3) B Tree (3) Coins (3) Dedup (3) Dropbox (3) Easy (3) Github (3) GoLang (3) Hard (3) Joseph (3) Jump Game (3) K (3) LogN (3) Minesweeper (3) NP Hard (3) O(N) Hard (3) Parser (3) Rectangle (3) Scala (3) SegmentFault (3) Shuffle (3) Skyline (3) Subtree (3) TSP (3) Trie + DFS (3) Word Ladder (3) bookkeeping (3) codebytes (3) Array Merge (2) BOJ (2) Bellman Ford (2) Bit Counting (2) Bit Mask (2) Bloom Filter (2) Clock (2) Codesays (2) DP - DFS (2) DP - Trie (2) DP-3D Table (2) DP-Classical (2) DP-i-k-j (2) Factor (2) GoHired (2) Graham Scan (2) Huffman Tree (2) Invariant (2) Islands (2) Lucene-Solr (2) Matrix Power (2) Median (2) Parentheses (2) Peak (2) Programming (2) Robot (2) Rosettacode (2) Search (2) SimHash (2) Sparse Table (2) Summary (2) TV (2) Tile (2) Tree Sum (2) Word Break (2) Word Graph (2) Word Trie (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) ? (1) Akka (1) BACK (1) BFS Hard (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Big Integer (1) Big Number (1) Binary (1) Bipartite (1) BitMap (1) BitMap index (1) BitSet (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Chinese (1) Clean Code (1) Cloest (1) Clone (1) Code Quality (1) Company-Epic (1) Company-Yelp (1) Concise (1) Concurrency (1) Custom Sort (1) DFS-Matrix (1) DI (1) DP-Difficult (1) DP-Graph (1) DP-MaxMin (1) DP-树形 (1) Database (1) Diagonal (1) Domino (1) Dr Dobb's (1) Duplicate (1) FST (1) Fraction (1) Funny (1) Game (1) Generation (1) GeoHash (1) Google APAC (1) Gray Code (1) HOJ (1) Hanoi (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Interview (1) Isomorphic (1) JDK8 (1) Knight (1) Kruskal (1) Kth Element (1) LeetCode -P (1) Linkedin (1) Local MinMax (1) Matrix BFS (1) Matrix Graph (1) Matrix+DP (1) MinHash (1) MinMax Heap (1) Monto Carlo (1) Multiple DFS (1) Next Element (1) Optimal Play (1) PAT (1) Parenthesis (1) Partition (1) Path Finding (1) Persistent (1) Power Set (1) PreProcess (1) Python (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Region (1) Resources (1) Revi (1) Robin (1) Selection (1) Similarity (1) Square (1) String DP (1) SubMatrix (1) Subsequence (1) Test (1) Test Cases (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tree Rotate (1) Trie vs Hash (1) Triplet (1) Two Stacks (1) Two-End-BFS (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) ZOJ (1) ZigZag (1) codevs (1) cos126 (1) javabeat (1) jum (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)