leetcode14 最长公共前缀
自己的解法
自己的解法就是先找出长度最短的字符串，然后以这个字符串为基准，去遍历其它字符串，看大家的前几位是否是相同的，遇到有不相同的直接返回，效率贼低。
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) {
return "";
}
if (strs.length == 1) {
return strs[0];
}
String shortStr = strs[0];
for (int i = 1; i < strs.length; i++) {
if (strs[i].length() < shortStr.length()) {
shortStr = strs[i];
}
}
StringBuffer res = new StringBuffer("");
for (int j = 0; j < shortStr.length(); j++) {
String a = shortStr.substring(j, j + 1);
for (int n = 0; n < strs.length; n++) {
String b = strs[n].substring(j, j + 1);
if (!a.equals(b)) {
return String.valueOf(res);
}
}
res.append(a);
}
return String.valueOf(res);
}
}
进阶解法
思路是，每次比较，两个字符串得出它们最长公共前缀，然后拿这个最长公共前缀去和其它字符串进行比较，直到和最后一个字符串比较完就可以了，期间每次比较都已经是拿之前字符串相同的部分在比较了，相对减少了比较次数。字符串获取第几个字符可以直接用charAt。
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length == 0)
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 ans;
}
return ans;
}
}
