LeetCode-14：最长公共前缀

本题为LeetCode中第14道题

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1:

1 2	输入: ["flower","flow","flight"] 输出: "fl"

示例 2:

1
2
3

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

1	所有输入只包含小写字母 a-z 。

public class Y_14_最长公共前缀 {
    public static void main(String[] args) {
        String[] strs = {"aca","cba"};
        String s = longestCommonPrefix_2(strs);
        System.out.println(s);

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

        String result = "";
        int count = 0;

        char temp;

        for(int i = 0;i<strs[0].length();i++){
            //取得第一个字符串的第一个字符
            char a = strs[0].charAt(i);

            for(int j = 1;j<strs.length;j++){

                if(i<strs[j].length()) {
                    char b = strs[j].charAt(i);
                    if(a==b){
                        count ++;
                    }
                }
            }
            if((count+1)==strs.length){
                result += a;
            }else{
                return result;
            }
            count=0;
        }
        return result;
    }
}

这道题呢其实比较简单，思路也很清晰，我们只需拿到第一个字符串，挨个取其第1个到最后一个字符，然后挨个和后面的比较，比如：你拿到第一个字符串的第一个字符，然后循环遍历取后面字符串的第一个字符，然后比较，然后拿第一个字符串的第2个字符，和后面的挨个比较即可

再来看另一道解法，效率会快很多

public static String longestCommonPrefix_2(String[] strs) {
        if(strs.length==0 || strs==null){
            return "";
        }
        char[] c = strs[0].toCharArray();
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i<c.length;i++){
            for(String s :strs){
                if(s.charAt(i)!=c[i] || i>s.length()){
                    return sb.toString();
                }
            }
            sb.append(c[i]);
        }
        return sb.toString();
    }

思路跟前面的一样，不过是在处理上做了手脚，还是很简单的！！！