题目描述
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例
输入: ["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 "";
}
}
注意：
- substring(a,b) 索引范围，前面的a可以取到，b取不到。
- 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。
