LeetCode 14 - Longest Common Prefix


https://leetcode.com/problems/longest-common-prefix/
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:
All given inputs are in lowercase letters a-z
X. Trie
Given a set of keys S = [S_1,S_2 \ldots S_n], find the longest common prefix among a string q and S. This LCP query will be called frequently.
We could optimize LCP queries by storing the set of keys S in a Trie. For more information about Trie, please see this article Implement a trie (Prefix trie). In a Trie, each node descending from the root represents a common prefix of some keys. But we need to find the longest common prefix of a string q and all key strings. This means that we have to find the deepest path from the root, which satisfies the following conditions: it is prefix of query string q each node along the path must contain only one child element. Otherwise the found path will not be a common prefix among all strings. * the path doesn't comprise of nodes which are marked as end of key. Otherwise the path couldn't be a prefix a of key which is shorter than itself.
In the worst case query q has length m and it is equal to all n strings of the array.
  • Time complexity : preprocessing O(S), where S is the number of all characters in the array, LCP query O(m).
    Trie build has O(S) time complexity. To find the common prefix of q in the Trie takes in the worst case O(m).
  • Space complexity : O(S). We only used additional S extra space for the Trie.
public String longestCommonPrefix(String q, String[] strs) {
    if (strs == null || strs.length == 0)
        return "";
    if (strs.length == 1)
        return strs[0];
    Trie trie = new Trie();
    for (int i = 1; i < strs.length; i++) {
        trie.insert(strs[i]);
    }
    return trie.searchLongestPrefix(q);
}

class TrieNode {

    // R links to node children
    private TrieNode[] links;

    private final int R = 26;

    private boolean isEnd;

    // number of children non null links
    private int size;

    public void put(char ch, TrieNode node) {
        links[ch - 'a'] = node;
        size++;
    }

    public int getLinks() {
        return size;
    }
    // assume methods containsKey, isEnd, get, put are implemented as it is described
    // in https://leetcode.com/articles/implement-trie-prefix-tree/)
}

public class Trie {

    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // assume methods insert, search, searchPrefix are implemented as it is described
    // in https://leetcode.com/articles/implement-trie-prefix-tree/)
    private String searchLongestPrefix(String word) {
        TrieNode node = root;
        StringBuilder prefix = new StringBuilder();
        for (int i = 0; i < word.length(); i++) {
            char curLetter = word.charAt(i);
            if (node.containsKey(curLetter) && (node.getLinks() == 1) && (!node.isEnd())) {
                prefix.append(curLetter);
                node = node.get(curLetter);
            } else
                return prefix.toString();

        }
        return prefix.toString();
    }

}

1. Create Trie data structure
2. Initialize with the input Strings
3. Search for longest common prefix until word is completed or there is nothing left.
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length <= 0){
            return "";
        }
        Trie trie = new Trie();
        for(int i = 0; i < strs.length; i++){
            trie.insert(strs[i]);
            if(strs[i].equals("") || strs[i].length() <= 0){
                return "";
            }
        }
        
        return trie.longestPrefix();
    }
class Trie{
    TrieNode root;
    public Trie(){
        root = new TrieNode();
    }
    public Trie(String s){
        root = new TrieNode();
        root.insert(s);
    }
    
    public void insert(String s){
        root.insert(s);   
    }
    
    public String longestPrefix(){
        StringBuilder prefix = new StringBuilder();
        TrieNode node = root;
        while(node != null && node.children.keySet().size() == 1 && !node.isWord){
            Set set = node.children.keySet();
            for(Iterator itr = set.iterator();itr.hasNext();){
                node = node.children.get(itr.next());
            }
            prefix.append(node.val);
        }
        return prefix.toString();
    }
}
class TrieNode{
    char val;
    boolean isWord;
    HashMap children = new HashMap();
    
    public void insert(String s){
        if(s == null || s.length() <=0){
            isWord = true;
            return;
        }
        char curr = s.charAt(0);
        TrieNode child = null;
        if(children.containsKey(curr)){
            child = children.get(curr);
            
        }else{
            child = new TrieNode();
            child.val = curr;
            children.put(curr, child);
        }
        String remainder = s.substring(1);
        child.insert(remainder);
        
    }
X. Bisection
In the worst case we have n equal strings with length m
  • Time complexity : O(S \cdot log(n)), where S is the sum of all characters in all strings.
    The algorithm makes log(n) iterations, for each of them there are S = m*n comparisons, which gives in total O(S \cdot log(n)) time complexity.
  • Space complexity : O(1). We only used constant extra space. 

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0)
        return "";
    int minLen = Integer.MAX_VALUE;
    for (String str : strs)
        minLen = Math.min(minLen, str.length());
    int low = 1;
    int high = minLen;
    while (low <= high) {
        int middle = (low + high) / 2;
        if (isCommonPrefix(strs, middle))
            low = middle + 1;
        else
            high = middle - 1;
    }
    return strs[0].substring(0, (low + high) / 2);
}

private boolean isCommonPrefix(String[] strs, int len) {
    String str1 = strs[0].substring(0, len);
    for (int i = 1; i < strs.length; i++)
        if (!strs[i].startsWith(str1))
            return false;
    return true;

}
X. Divide and conquer
In the worst case we have n equal strings with length m
  • Time complexity : O(S), where S is the number of all characters in the array, S = m*n Time complexity is 2 \cdot T\left ( \frac{n}{2} \right ) + O(m). Therefore time complexity is O(S). In the best case this algorithm performs O(minLen \cdot n) comparisons, where minLen is the shortest string of the array
  • Space complexity : O(m \cdot log(n))
    There is a memory overhead since we store recursive calls in the execution stack. There are log(n)recursive calls, each store need m space to store the result, so space complexity is O(m \cdot log(n))
public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0)
        return "";
    return longestCommonPrefix(strs, 0, strs.length - 1);
}

private String longestCommonPrefix(String[] strs, int l, int r) {
    if (l == r) {
        return strs[l];
    } else {
        int mid = (l + r) / 2;
        String lcpLeft = longestCommonPrefix(strs, l, mid);
        String lcpRight = longestCommonPrefix(strs, mid + 1, r);
        return commonPrefix(lcpLeft, lcpRight);
    }
}

String commonPrefix(String left, String right) {
    int min = Math.min(left.length(), right.length());
    for (int i = 0; i < min; i++) {
        if (left.charAt(i) != right.charAt(i))
            return left.substring(0, i);
    }
    return left.substring(0, min);

}

http://www.programcreek.com/2014/02/leetcode-longest-common-prefix-java/
To solve this problem, we need to find the two loop conditions. One is the length of the shortest string. The other is iteration over every element of the string array.
public String longestCommonPrefix(String[] strs) {
    if(strs == null || strs.length == 0)
        return "";
 
    int minLen=Integer.MAX_VALUE;
    for(String str: strs){
        if(minLen > str.length())
            minLen = str.length();
    }
    if(minLen == 0) return "";
 
    for(int j=0; j<minLen; j++){
        char prev='0';
        for(int i=0; i<strs.length ;i++){
            if(i==0) {
                prev = strs[i].charAt(j);
                continue;
            }
 
            if(strs[i].charAt(j) != prev){
                return strs[i].substring(0, j);
            }
        }
    }
 
    return strs[0].substring(0,minLen);
}
http://www.jiuzhang.com/solutions/longest-common-prefix/
    // 1. Method 1, start from the first one, compare prefix with next string, until end;
    // 2. Method 2, start from the first char, compare it with all string, and then the second char
    // I am using method 1 here
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for(int i = 1; i < strs.length; i++) {
            int j = 0;
            while( j < strs[i].length() && j < prefix.length() && strs[i].charAt(j) == prefix.charAt(j)) {
                j++;
            }
            if( j == 0) {
                return "";
     }
            prefix = prefix.substring(0, j);
        }
        return prefix;
    }
https://leetcode.com/discuss/32176/fast-and-simple-java-code-231ms
public String longestCommonPrefix(List<String> strs) { if(strs.size()==0) return ""; StringBuilder lcp=new StringBuilder(); for(int i=0;i<strs.get(0).length();i++){ char c=strs.get(0).charAt(i); for(String s:strs){ if(s.length()<i+1||c!=s.charAt(i)) return lcp.toString();//\\ } lcp.append(c); } return lcp.toString(); }

Rather than building the string for common prefix, you can just record the longest prefix's length, then return the substring from first character till that length, which can save a bit time perhaps.
var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return "";
    if (strs.length === 1) return strs[0];

    for (var i = 0; i < strs[0].length; i++) {
        for (var j = 1; j < strs.length; j++) {
            if (strs[j].length <= i || strs[j][i] !== strs[0][i]) {
                return strs[0].substring(0, i);
            }
        }
    }
    return strs[0];
};
https://leetcode.com/discuss/89652/my-2ms-java-solution-may-help-u
doesn't really help to get the min len
public String longestCommonPrefix(String[] strs) { int len = strs.length; if (len == 0) return ""; int minlen = 0x7fffffff; for (int i = 0; i < len; ++i) minlen = Math.min(minlen, strs[i].length());//\\ for (int j = 0; j < minlen; ++j) for (int i = 1; i < len; ++i) if (strs[0].charAt(j) != strs[i].charAt(j)) return strs[0].substring(0, j); return strs[0].substring(0, minlen); }
Don't use trie.
http://comproguide.blogspot.com/2014/05/finding-longest-common-prefix-from.html

string longestCommonPrefix(vector<string> & strVect)




{




string result;








if( strVect.size() > 0 ) //proceed only if not empty




result = strVect[0]; //Assume first string as longest common prefix




int i,j;




//in each iteration try to match the whole prefix; if not matching reduce it




for( i = 1; i < strVect.size(); i++ )




{




int m = min( result.size(), strVect[i].size() );




for( j = 0; j < m; j++ )




{




if( result[j] != strVect[i][j] )




break;




}




result = result.substr(0,j);




//this condition will prevent further checking of the prefix is already empty




if( result.empty() )




break;




}




return result;




}
X. Sort
https://leetcode.com/problems/longest-common-prefix/discuss/6924/Sorted-the-array-Java-solution-2-ms
Sort the array first, and then you can simply compare the first and last elements in the sorted array.


Not a good solution, there's no need to sort the entire array since you're only using the min and max values. You can just find the min and max directly in a single pass of the array.
Stylistically, the else statement within the for is unnecessary if you just move your if check into the for loop check. You also don't need a StringBuilder, all you need is the value of i then call min.substring using it
    public String longestCommonPrefix(String[] strs) {
        StringBuilder result = new StringBuilder();

        if (strs!= null && strs.length > 0){

            Arrays.sort(strs);

            char [] a = strs[0].toCharArray();
            char [] b = strs[strs.length-1].toCharArray();

            for (int i = 0; i < a.length; i ++){
                if (b.length > i && b[i] == a[i]){
                    result.append(b[i]);
                }
                else {
                    return result.toString();
                }
            }
        return result.toString();
    }
Nice but you don't have to sort the array to get the first and last string in the sorted array. It will cost O(n log n).


Also, we can use .charAt() to get the specific character in the string, it also cost O(1). Therefore, we don't have to create an extra char array.
    public String longestCommonPrefix(String[] strs) {
        if (strs == null)       return null;
        if (strs.length == 0)   return "";
        
        String first = strs[0], last = strs[0];
        
        for (String str : strs) {
            if (str.compareTo(first) < 0)
                first = str;
            if (str.compareTo(last) > 0)
                last = str;
        }
        
        int i = 0, len = Math.min(first.length(), last.length());
        
        while (i < len && first.charAt(i) == last.charAt(i))
            i++;
        
        return first.substring(0, i);

X.
Approach 1: Horizontal scanning
https://leetcode.com/articles/longest-common-prefix/
  • Time complexity : O(S) , where S is the sum of all characters in all strings.
    In the worst case all n strings are the same. The algorithm compares the string S1 with the other strings [S_2 \ldots S_n] There are S character comparisons, where S is the sum of all characters in the input array.
public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0)
        return "";
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++)
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty())
                return "";
        }
    return prefix;

}

Approach 2: Vertical scanning
Imagine a very short string is at the end of the array. The above approach will still do S comparisons. One way to optimize this case is to do vertical scanning. We compare characters from top to bottom on the same column (same character index of the strings) before moving on to the next column.
  • Time complexity : O(S) , where S is the sum of all characters in all strings. In the worst case there will be n equal strings with length m and the algorithm performs S = m*n character comparisons. Even though the worst case is still the same as Approach 1, in the best case there are at most n*minLen comparisons where minLen is the length of the shortest string in the array.
public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0)
        return "";
    for (int i = 0; i < strs[0].length(); i++) {
        char c = strs[0].charAt(i);
        for (int j = 1; j < strs.length; j++) {
            if (i == strs[j].length() || strs[j].charAt(i) != c)
                return strs[0].substring(0, i);
        }
    }
    return strs[0];
}

Also read http://fisherlei.blogspot.com/2012/12/leetcode-longest-common-prefix.html
Read full article from LeetCode: Longest Common Prefix in Java | Param's Blog
at
Labels: , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts