問題描述
編寫一個函數(shù)來查找字符串數(shù)組中的最長公共前綴篡悟。
如果不存在公共前綴致板，返回空字符串 ""。
示例 1:
輸入: ["flower","flow","flight"]
輸出: "fl"
示例 2:
輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴坊夫。
說明:
所有輸入只包含小寫字母 a-z 砖第。
解答
暴力匹配法，感覺挺sb的环凿，提交顯示執(zhí)行只用了1ms……
public static String solution(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
StringBuilder stringBuilder = new StringBuilder();
// 遍歷數(shù)組第一個字符串的字符
for (int i = 0; i < strs[0].length(); i++) {
// 遍歷數(shù)組中其余的字符串
for (int j = 1; j < strs.length; j++) {
// 如果字符串長度過小梧兼，或者字符不匹配，返回當前的stringBuilder
// 長度的判斷放在前面智听，避免后面的索引越界
if (strs[j].length() < i + 1 || strs[j].charAt(i) != strs[0].charAt(i)) {
return stringBuilder.toString();
}
}
// 所有字符串都匹配了該字符羽杰，拼接到stringBuilder中
stringBuilder.append(strs[0].charAt(i));
}
return stringBuilder.toString();
}
可以不使用stringbuilder渡紫，記錄下i的值，使用substring返回即可
public static String solution1(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
for (int i = 0; i < strs[0].length(); i++) {
char c = strs[0].charAt(i);
for (int j = 1; j < strs.length; j++) {
if (strs[j].length() == i || strs[j].charAt(i) != c) {
return strs[0].substring(0, i);
}
}
}
return strs[0];
}
一個0ms的解法：遍歷數(shù)組考赛，判斷第一個字符串是否是前綴惕澎，如果不是：將第一個字符串的最后一個字符去掉，直到是本次遍歷的字符串的前綴為止颜骤，然后繼續(xù)往下遍歷數(shù)組唧喉。
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) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
return prefix;
}
