No.14 最长公共前缀（Java）

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

示例

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

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

解法一：子串比较

思路：以长度最短的字符串min_str为基准，判断剩下的N-1个字符串是否包含该子串。初始时将子串长度设置为min_str.length()，若不符合，将寻找的长度-1。
代码：运行时间2ms，内存消耗35.3MB。

class Solution {
    public String longestCommonPrefix(String[] strs) {
      //求出最短的字符串长度
        if(strs == null || strs.length==0) return "";
        int min_len = strs[0].length();
        for(int j=1;j<strs.length;j++) 
            if(strs[j].length()<min_len) min_len = strs[j].length();
        for(int i=min_len-1;i>=0;--i) 
        {
            boolean flag = true;
            for(int j=1;j<strs.length;j++) {
            if(!strs[0].substring(0,i+1).equals(strs[j].substring(0,i+1)))
                {   
                    flag = false;
                    break;
                }
            }
            if(flag)  
                return new StringBuilder(strs[0].substring(0,i+1)).toString();
        }
        return "";
    }
}  

注意：

1. substring(a,b) 索引范围，前面的a可以取到，b取不到。
2. str1 == str2 表示指向同一个对象，str1.equals(str2)表示值相等。

解法二：水平扫描

思路：首先将前两组字符串取最长公共前缀，然后将该前缀与第三组字符串取公共前缀......直到新的公共前缀为空，算法结束，得到最终的最长公共前缀。（即一直取交集）
代码：

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length==0 || strs ==null) return "";
        String ans = strs[0];
        for(int i=1;i<strs.length;i++){
            int j=0;
            for(;j<ans.length() && j<strs[i].length();j++)
            {
                if(ans.charAt(j)!=strs[i].charAt(j)) break;
            }
            ans = ans.substring(0,j);
            //不存在公共前缀
            if(ans.equals("")) return "";
        }
        return ans;
    }
}

执行：用时3ms,内存消耗35.8MB。