題目信息
編寫一個(gè)函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴朵你。如果不存在公共前綴，返回空字符串 ""抡医。
示例 1：
輸入：strs = ["flower","flow","flight"]
輸出："fl"
示例 2：
輸入：strs = ["dog","racecar","car"]
輸出：""
解釋：輸入不存在公共前綴。
解題思路
- 暴力破解：依次比較所有元素得出公共前綴
- 無效操作分析：當(dāng)數(shù)組較前元素沒有公共前綴后，后面的元素就沒有繼續(xù)比較的意義了搁嗓。
- 優(yōu)化方法：
- 考慮邊界：
- 數(shù)組為空，公共前綴為“”
- 數(shù)組有且只有一個(gè)元素腺逛，公共前綴為該元素本身。
- 編碼實(shí)現(xiàn)
代碼
解法一：橫向比較
class Solution {
public String longestCommonPrefix(String[] strs) {
// 邊界檢查
if (strs == null || strs.length == 0) {
return "";
}
// 初始化前綴為第一個(gè)元素
String prefix = strs[0];
int count = strs.length;
for (int i = 1; i < count; i++) {
prefix = longestCommonPrefix(prefix, strs[i]);
// 已經(jīng)沒有前綴后就沒有繼續(xù)比較的必要了
if (prefix.length() == 0) {
break;
}
}
return prefix;
}
/**
* 返回當(dāng)前字符與前綴的共同部分
*/
private String longestCommonPrefix(String str1, String str2) {
// 優(yōu)化：不必比較所有字符安疗，比較完當(dāng)前已知前綴后即可得知新的公共前綴
int length = Math.min(str1.length(), str2.length());
int index = 0;
while (index < length && str1.charAt(index) == str2.charAt(index)) {
index++;
}
return str1.substring(0, index);
}
}
解法二：縱向比較
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
int length = strs[0].length();
int count = strs.length;
for (int i = 0; i < length; i++) {
char c = strs[0].charAt(i);
for (int j = 1; j < count; j++) {
if (i == strs[j].length() || strs[j].charAt(i) != c) {
return strs[0].substring(0, i);
}
}
}
return strs[0];
}
}
題目來源：力扣（LeetCode）
題目鏈接：https://leetcode-cn.com/problems/longest-common-prefix
商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)荐类，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
