14. Longest Common Prefix

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

String类题目

##Approach 1: Horizontal scanning

依次比较，若string不含之前的common prefix，将prefix从尾部删减，直到找到新的common prefix。

public class Solution {
    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) {
                // if not contain prefix, remove the last char of prefix
                prefix = prefix.substring(0, prefix.length()-1);
                if(prefix.isEmpty()) {
                    // if prefix is "", return
                    return prefix;
                }
            }
        }
        return prefix;
    }
}

##Approach 2: Vertical scanning

上面的方法的不足之处在于若最后一个string很短，则浪费了大量的comparison。 因此可以将所有string同时进行比较,找common prefix。

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0) {
            return "";
        }
        
        for(int i = 0; i < strs[0].length(); i++) {
            for(int j = 1; j < strs.length; j++) {
                if(i == strs[j].length() || strs[0].charAt(i) != strs[j].charAt(i)) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}