Leetcode - Longest Common Prefix

Question:

Paste_Image.png

My code:

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null)
            return null;
        if (strs.length == 0)
            return "";
        if (strs.length == 1)
            return strs[0];
        
        int minLength = Integer.MAX_VALUE;
        for (int i = 0; i < strs.length; i++) {
            if (minLength > strs[i].length())
                minLength = strs[i].length();
        }
        
        String result = "";
        boolean isOver = false;
        for (int i = 0; i < minLength; i++) {
            for (int j = 0; j < strs.length - 1; j++) {
                if (strs[j].charAt(i) != strs[j + 1].charAt(i)) {
                    isOver = true;
                    break;
                }
            }
            if (!isOver)
                result += strs[0].charAt(i);
            else
                break;
        }
        return result;
    }
}

My test result:

Paste_Image.png

侮辱智商的题目。不爆粗口了。

**
总结：简书，你上传照片这一个功能怎么老是这么卡。优化下行吗？
**

Anyway, Good luck, Richardo!

这道题目竟然没做出来，感觉自己的思考能力越来越差了，碰到新题，第一个想到的就是看答案。
this is not right!

My code:

Horizontal scanning

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || 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.length() == 0) {
                    return "";
                }
            }
        }
        return prefix;
    }
}

Vertical Scanning
My code:

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        int i = 0;
        while (i < strs[0].length()) {
            char curr = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (i < strs[j].length() && strs[j].charAt(i) == curr) {
                    continue;
                }
                else {
                    return strs[0].substring(0, i);
                }
            }
            i++;
        }
        return strs[0];
    }
}

reference:
https://leetcode.com/articles/longest-common-prefix/

这篇文章分析的很好。
还有两种方法：
一个是 divide and conquer,把strs[] 分成两块去找LCP,然后再merge
一个是 binary search, 先找到最短字符串，s[0, end]
然后看 s[0, mid] 是不是 CP,
如果是， begin = mid,
如果不是， end = mid - 1
以此类推。

然后最后有个follow up,
如果给定一个 strs[], 还有一个输入string p,
找 p 在 strs[] 中的LCP
怎么做？

最快的方法就是建Trie,然后顺着 p 在Trie里面走下去，每走一步，当前结点必须只有一个link，而且必须不是end point
然后找到 LCP

然后还有种方法解决这道题目。
将 strs[] 全部排序，然后比较第一个和最后一个字符串，找 LCP

My code:

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        Arrays.sort(strs);
        String s1 = strs[0];
        String s2 = strs[strs.length - 1];
        int i = 0;
        for (; i < s1.length(); i++) {
            if (i < s2.length() && s1.charAt(i) == s2.charAt(i)) {
                continue;
            }
            else {
                break;
            }
        }
        return s1.substring(0, i);
    }
}

Anyway, Good luck, Richardo! -- 09/17/2016