LongestCommonPrefix [source code]

public class LongestCommonPrefix {
static
/******************************************************************************/
public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        if (strs.length == 1) return strs[0];
        int pos = 0;
        while (true) {
            for (int i = 1; i < strs.length; i++) {
                if (pos == strs[i].length() ||
                    pos == strs[0].length() ||
                    strs[i].charAt(pos) != strs[0].charAt(pos)) return strs[0].substring(0, pos);
            }
            pos++;
        }
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        LongestCommonPrefix.Solution tester = new LongestCommonPrefix.Solution();
        String[][] inputs = {
            {"abc", "ab", "abcd"},
            {"", "dab"},
            {},
        };
        for (String[] strs : inputs) {
            Printer.openColor("red");
            Printer.array (strs);
            Printer.closeColor();
            System.out.println(" -> " + tester.longestCommonPrefix(strs));
        }
    }
}

题目本身还是很简单的, 就是一个穷搜, 想不到更好的办法;
注意这里的一个小技巧, 就是 || 在 if 的 header 里面的应用的时候, 一定要注意顺序! 一个普遍的rule of thumb好像是, 一般都是index本身的 constraint 放在前面的比较多; 不过&& 和 || 的区别是前面的 index constraint 内容不一样: || 的时候这个 constraint 一般限制的是非法(针对array access); && 的 constraint 一般针对的是合法;

最后的速度是13ms (35%), 有点不太好;

这个是 submission 最优解 10ms:

public class Solution {  
    public String longestCommonPrefix(String[] strs) {  
        if(strs == null || strs.length ==0) return "";  

        //找陣列裡的 最長的共同的前綴  
        //讓pre = strs[0]  
        //如果indexof(pre) = -1 代表沒找到  
        //就讓pre = pre.substring(0, pre.length()-1)  
        //直到找到從0的位置開始的pre  
        //如果沒有的話pre會等於空字串  

        String pre = strs[0];  
        for(int i = 0; i<strs.length; i++){  
            while(strs[i].indexOf(pre) !=0){  
                pre = pre.substring(0, pre.length()-1);  
            }  
        }  

        return pre;  
    }  
}

感觉其实本身的想法也没有什么特别的地方, 穷搜是从长度为0开始搜, 他这个是从最长长度开始搜; 我感觉他这个算法还是容易被 break 的:

"abcdefg"  
"abcdefg"  
"abcdefg"  
"abcdefg"  
"abcdefg"  
"abcdefg"  
"a"

这样的输出最后就会有一个worst-case的速度;

不过 LeetCode 的 case 好像比较照顾这个思路而已;

这个是用 StringBuffer 加速了一下的, 快了1ms:

public class Solution {  
    public String longestCommonPrefix(String[] strs) {  
        int len = strs.length;  
        if( len == 0)  
            return "";  
        if(len == 1)  
            return strs[0];  
        StringBuffer test = new StringBuffer(strs[0]);  
        for(int i=1;i<len;i++){  
            if(strs[i].startsWith(test.toString()))  
                continue;  
            test.setLength(test.length()-1);  
            i--;  
        }  
        return test.toString();  
    }  
}

editorial里面把他们这种做法叫做horizontal scanning, 我这种叫做vertical scanning;

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

看看就行, 速度并没有什么优越性, 不过提供了另外一种思路;

解4是一个binary search的解法:

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

这个好像还是有点意思的, 这个算法最后可能可以加速? 就是不知道starts with是怎么实现的? 有直接单个 char 的比较快吗?

editorial 里面还加了一个 Follow-Up: 给定这个 list, 然后给一个 String q, 然后找他们的LCP. 这个 query 会被频繁调用;

这个就是一个查表类的问题了: list 本身整个就是一个类似 dictionary 的东西, 你要做的其实就是把它放到一个合适的数据结构里面, 然后每一个 q 进来就是直接查表就行了. 实际这里的这个数据结构用 trie 比较好, 毕竟是做 dictionary:

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

这个代码没有仔细看, 有空再看吧.

discussion 里面一个奇葩的解: sort

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

Comparison between two strings are O(k) k is the length of two strings
so the complexity of this algorithm is O(nlogn k)
It's slower than other solutions, other solutions don't require sorting and they are mostly O(n k) complexity

这个算法也是看看就好;

Problem Description

Write a function to find the longest common prefix string amongst an array of strings.

Difficulty:Easy
Total Accepted:183K
Total Submissions:582.3K
Contributor: LeetCode
Companies
yelp
Related Topics
string