## Friday, June 24, 2016

### Longest Common Prefix

```Input  : {“geeksforgeeks”, “geeks”, “geek”, “geezer”}
Output : "gee"

Input  : {"apple", "ape", "april"}
Output : "ap"```
http://www.geeksforgeeks.org/longest-common-prefix-set-5-using-trie/
`// Counts and returns the number of children of the`
`// current node`
`int` `countChildren(``struct` `TrieNode *node, ``int` `*index)`
`{`
`    ``int` `count = 0;`
`    ``for` `(``int` `i=0; i<ALPHABET_SIZE; i++)`
`    ``{`
`        ``if` `(node->children[i] != NULL)`
`        ``{`
`            ``count++;`
`            ``*index = i;`
`        ``}`
`    ``}`
`    ``return` `(count);`
`}`

`// Peform a walk on the trie and return the`
`// longest common prefix string`
`string walkTrie(``struct` `TrieNode *root)`
`{`
`    ``struct` `TrieNode *pCrawl = root;`
`    ``int` `index;`
`    ``string prefix;`

`    ``while` `(countChildren(pCrawl, &index) == 1)`
`    ``{`
`        ``pCrawl = pCrawl->children[index];`
`        ``prefix.push_back(``'a'``+index);`
`    ``}`
`    ``return` `(prefix);`
`}`

`// A Function to construct trie`
`void` `constructTrie(string arr[], ``int` `n, ``struct` `TrieNode *root)`
`{`
`    ``for` `(``int` `i = 0; i < n; i++)`
`        ``insert (root, arr[i]);`
`    ``return``;`
`}`

`// A Function that returns the longest common prefix`
`// from the array of strings`
`string commonPrefix(string arr[], ``int` `n)`
`{`
`    ``struct` `TrieNode *root = getNode();`
`    ``constructTrie(arr, n, root);`

`    ``// Perform a walk on the trie`
`    ``return` `walkTrie(root);`
`}`
http://www.geeksforgeeks.org/longest-common-prefix-set-4-binary-search/
1. Find the string having the minimum length. Let this length be L.
2. Perform a binary search on any one string (from the input array of strings). Let us take the first string and do a binary search on the characters from the index – 0 to L-1.
3. Initially, take low = 0 and high = L-1 and divide the string into two halves – left (low to mid) and right (mid+1 to high).
4. Check whether all the characters in the left half is present at the corresponding indices (low to mid) of all the strings or not. If it is present then we append this half to our prefix string and we look in the right half in a hope to find a longer prefix.(It is guaranteed that a common prefix string is there.)
5. Otherwise, if all the characters in the left half is not present at the corresponding indices (low to mid) in all the strings, then we need not look at the right half as there is some character(s) in the left half itself which is not a part of the longest prefix string. So we indeed look at the left half in a hope to find a common prefix string. (It may be possible that we don’t find any common prefix string)
Time Complexity :
The recurrence relation is
`T(M) = T(M/2) + O(MN) `
where
```N = Number of strings
M = Length of the largest string string
```
So we can say that the time complexity is O(NM log M)
Auxiliary Space: To store the longest prefix string we are allocating space which is O(N) where, N = length of the largest string among all the strings
`bool` `allContainsPrefix(string arr[], ``int` `n, string str,`
`                       ``int` `start, ``int` `end)`
`{`
`    ``for` `(``int` `i=0; i<=n-1; i++)`
`        ``for` `(``int` `j=start; j<=end; j++)`
`            ``if` `(arr[i][j] != str[j])`
`                ``return` `(``false``);`
`    ``return` `(``true``);`
`}`

`// A Function that returns the longest common prefix`
`// from the array of strings`
`string commonPrefix(string arr[], ``int` `n)`
`{`
`    ``int` `index = findMinLength(arr, n);`
`    ``string prefix; ``// Our resultant string`

`    ``// We will do an in-place binary search on the`
`    ``// first string of the array in the range 0 to`
`    ``// index`
`    ``int` `low = 0, high = index;`

`    ``while` `(low <= high)`
`    ``{`
`        ``// Same as (low + high)/2, but avoids overflow`
`        ``// for large low and high`
`        ``int` `mid = low + (high - low) / 2;`

`        ``if` `(allContainsPrefix (arr, n, arr[0], low, mid))`
`        ``{`
`            ``// If all the strings in the input array contains`
`            ``// this prefix then append this substring to`
`            ``// our answer`
`            ``prefix = prefix + arr[0].substr(low, mid-low+1);`

`            ``// And then go for the right part`
`            ``low = mid + 1;`
`        ``}`

`        ``else` `// Go for the left part`
`            ``high = mid - 1;`
`    ``}`

`    ``return` `(prefix);`
`}`
http://www.geeksforgeeks.org/longest-common-prefix-set-3-divide-and-conquer/
Time Complexity : Since we are iterating through all the characters of all the strings, so we can say that the time complexity is O(N M) where,
```N = Number of strings
M = Length of the largest string string```
Auxiliary Space : To store the longest prefix string we are allocating space which is O(M Log N).
`// A Utility Function to find the common prefix between`
`// strings- str1 and str2`
`string commonPrefixUtil(string str1, string str2)`
`{`
`    ``string result;`
`    ``int` `n1 = str1.length(), n2 = str2.length();`

`    ``// Compare str1 and str2`
`    ``for` `(``int` `i=0, j=0; i<=n1-1&&j<=n2-1; i++,j++)`
`    ``{`
`        ``if` `(str1[i] != str2[j])`
`            ``break``;`
`        ``result.push_back(str1[i]);`
`    ``}`

`    ``return` `(result);`
`}`

`// A Function that returns the longest common prefix`
`// from the array of strings`
`string commonPrefix (string arr[], ``int` `n)`
`{`
`    ``string prefix =  arr[0];`

`    ``for` `(``int` `i=1; i<=n-1; i++)`
`        ``prefix = commonPrefixUtil(prefix, arr[i]);`

`    ``return` `(prefix);`
`}`
Time Complexity : Since we are iterating through all the strings and for each string we are iterating though each characters, so we can say that the time complexity is O(N M) where,
```N = Number of strings
M = Length of the largest string string ```
Auxiliary Space : To store the longest prefix string we are allocating space which is O(M).
`string commonPrefix(string arr[], ``int` `n)`
`{`
`    ``int` `minlen = findMinLength(arr, n);`

`    ``string result; ``// Our resultant string`
`    ``char` `current;  ``// The current character`

`    ``for` `(``int` `i=0; i<minlen; i++)`
`    ``{`
`        ``// Current character (must be same`
`        ``// in all strings to be a part of`
`        ``// result)`
`        ``current = arr[0][i];`

`        ``for` `(``int` `j=1 ; j<n; j++)`
`            ``if` `(arr[j][i] != current)`
`                ``return` `result;`

`        ``// Append to result`
`        ``result.push_back(current);`
`    ``}`

`    ``return` `(result);`
`}`
How is this algorithm better than the “Word by Word Matching” algorithm ?-
In Set 1 we discussed about the “Word by Word Matching” Algorithm.
Suppose you have the input strings as- “geeksforgeeks”, “geeks”, “geek”, “geezer”, “x”.
Now there is no common prefix string of the above strings. By the “Word by Word Matching” algorithm discussed in Set 1, we come to the conclusion that there is no common prefix string by traversing all the strings. But if we use this algorithm, then in the first iteration itself we will come to know that there is no common prefix string, as we don’t go further to look for the second character of each strings.
This algorithm has a huge advantage when there are too many strings.
Time Complexity : Since we are iterating through all the characters of all the strings, so we can say that the time complexity is O(N M) where,
```N = Number of strings
M = Length of the largest string string ```
Auxiliary Space : To store the longest prefix string we are allocating space which is O(M).

## Labels

GeeksforGeeks (1109) LeetCode (1095) Review (846) Algorithm (795) to-do (633) LeetCode - Review (574) Classic Algorithm (324) Dynamic Programming (294) Classic Interview (288) Google Interview (242) Tree (145) POJ (139) Difficult Algorithm (132) LeetCode - Phone (127) EPI (125) Bit Algorithms (120) Different Solutions (120) Lintcode (113) Smart Algorithm (109) Math (108) HackerRank (89) Binary Search (83) Binary Tree (82) Graph Algorithm (76) Greedy Algorithm (73) DFS (71) Stack (65) Interview Corner (61) List (58) BFS (54) Codility (54) ComProGuide (52) Trie (49) USACO (46) Interval (45) LeetCode Hard (42) ACM-ICPC (41) Data Structure (40) Knapsack (40) Jobdu (39) Matrix (39) String Algorithm (38) Union-Find (37) Backtracking (36) Codeforces (36) Must Known (36) Sort (35) Array (33) Segment Tree (33) Sliding Window (33) prismoskills (33) HDU (31) Priority Queue (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Company-Airbnb (29) Company-Zenefits (28) Palindrome (28) to-do-must (28) Graph (27) Random (27) GeeksQuiz (25) Logic Thinking (25) Pre-Sort (25) Time Complexity (25) hihocoder (25) Queue (24) Company-Facebook (23) High Frequency (23) TopCoder (23) Algorithm Game (22) Bisection Method (22) Hash (22) DFS + Review (21) Two Pointers (21) Brain Teaser (20) CareerCup (20) LeetCode - DP (20) Merge Sort (20) O(N) (20) Follow Up (19) UVA (19) Ordered Stack (18) Probabilities (18) Company-Uber (17) Game Theory (17) Topological Sort (17) Codercareer (16) Heap (16) Shortest Path (16) String Search (16) Tree Traversal (16) itint5 (16) Difficult (15) Iterator (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) Combination (12) Modify Tree (12) Reconstruct Tree (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Graph DFS (11) LCA (11) Miscs (11) Princeton (11) Proof (11) Rolling Hash (11) Tree DP (11) X Sum (11) 挑战程序设计竞赛 (11) Bisection (10) Bucket Sort (10) Coin Change (10) DFS+Cache (10) HackerRank Easy (10) O(1) Space (10) SPOJ (10) Theory (10) TreeMap (10) Tutorialhorizon (10) Mathblog (9) Max-Min Flow (9) Prefix Sum (9) Quick Sort (9) Simulation (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) 穷竭搜索 (8) Expression (7) Game Nim (7) Graph BFS (7) Hackerearth (7) Inversion (7) Quick Select (7) Radix Sort (7) TreeSet (7) n00tc0d3r (7) 蓝桥杯 (7) DFS+DP (6) DP - Tree (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) 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) Graph Cycle (5) Immutability (5) Java (5) Maze (5) Pre-Sum (5) Quadtrees (5) Quora (5) Subarray Sum (5) Sudoku (5) Sweep Line (5) Word Search (5) jiuzhang (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Abbreviation (4) Anagram (4) Anagrams (4) Chess Game (4) Distributed (4) Flood fill (4) Histogram (4) MST (4) MinMax (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) A Star (3) B Tree (3) Coins (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Github (3) GoLang (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) 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-3D Table (2) DP-Classical (2) DP-i-k-j (2) DP-树形 (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) 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) Akka (1) BACK (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) DP-Difficult (1) DP-Graph (1) DP-MaxMin (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) 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) 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) Robin (1) Selection (1) Similarity (1) Square (1) String DP (1) SubMatrix (1) Subsequence (1) TSP (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)