最長公共前綴
題目描述：編寫一個函數(shù)來查找字符串數(shù)組中的最長公共前綴甥角。
如果不存在公共前綴，返回空字符串 ""治宣。
示例說明請見LeetCode官網(wǎng)丹擎。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-common-prefix/
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)秒啦，非商業(yè)轉(zhuǎn)載請注明出處熬粗。
解法一：字符數(shù)組法
把第一個字符串放到字符數(shù)組chars中，從第二個字符串開始余境，挨個字符遍歷比較驻呐，得到每次不相等的索引位置p，如果p-1小于0芳来，則表示沒有公共前綴含末；遍歷后面的字符串，重復(fù)這一過程即舌。 中間只要p-1小于0佣盒，直接返回空字符串，沒有公共前綴顽聂。 遍歷結(jié)束后肥惭，獲取chars數(shù)組中從0到p-1位置的字符，返回即為最長公共前綴紊搪。
public class Solution {
public static String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0 || strs[0] == null || strs[0].length() == 0) {
return "";
}
char[] chars = strs[0].toCharArray();
int maxIndex = strs[0].length() - 1;
for (int i = 1; i < strs.length && maxIndex >= 0; i++) {
String curStr = strs[i];
if (curStr == null || curStr.length() == 0) {
return "";
}
int curMax = maxIndex;
for (int j = 0; j < curStr.length() && j <= curMax && maxIndex >= 0; j++) {
if (curStr.charAt(j) != chars[j]) {
maxIndex = j - 1;
break;
} else {
maxIndex = j;
}
}
}
if (maxIndex < 0) {
return "";
}
StringBuilder result = new StringBuilder();
for (int i = 0; i <= maxIndex; i++) {
result.append(chars[i]);
}
return result.toString();
}
public static void main(String[] args) {
System.out.println(longestCommonPrefix(new String[]{"flower", "flow", "flight"}));
System.out.println(longestCommonPrefix(new String[]{"ab", "a"}));
}
}
