Longest Common Prefix

LCP(S1,S2,..Sn)=LCP(LCP(LCP(S1,S2),S3),...Sn)

1. 遍历S数组，不断更新prefix

   • startsWith 等价于 indexOf(prefix) == 0
   • removeLast 通过substing(0, prefix.length()-1)
   • O(S)，其中S为数组里所有chars的个数，worstcase,当所有string都相同时候，总共需要比较S次

     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;
     }
     

2. 遍历prefix，这里即为strs[0], vertical scanning

   • 当strs中存在非常短的数组的时候，若还是用上述方法，依然需要比较S次。于是这里考虑把所有string左对齐，从头开始比较
   • 复杂度仍为O(S)，但是在best case的情况下，只需要n * minLen次比较即可

     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)
                //第i位也是不满足的
                return strs[0].substring(0, i);             
        }
     }
     return strs[0];
     }
     

3. Divide & Conquer

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);
}

Follow ups

Given a set of keys S = [S1,S2...Sn], 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

• tire搜寻的prefix路径中经过的每个node，必须有且只有一个子元素，否则无法成为所有String的Common prefix
• prefix中经过的每个node,不能是某个string的结束位置。否则prefix则会比string长了

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();
    }
}