1.算法題目
編寫一個函數(shù)來查找字符串數(shù)組中的最長公共前綴侠草。
如果不存在公共前綴，返回空字符串 ""。
示例 1:
輸入: ["flower","flow","flight"]
輸出: "fl"
示例 2:
輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴。
說明:
所有輸入只包含小寫字母 a-z 赘娄。
2.算法思路
首先總結一下公共前綴的規(guī)律，所謂字符串的公共前綴宏蛉，指的是不同的字符串相同位置上的字符都相等的最大子字符串。借助這個規(guī)律得出的算法思路如下：
- 逐位比較：首先找出最短的字符串長度（因為最長公共前綴的長度不會大于最短字符串的長度）性置，然后遍歷字符串數(shù)組從前到后每個位置上面的字符是否相等拾并，遍歷到都相等時記錄公共前綴；
- 水平掃描：從前往后枚舉字符串的每一列鹏浅，先比較每個字符串相同列上的字符（即不同字符串相同下標的字符）然后再進行對下一列的比較嗅义。
3.算法代碼
根據(jù)逐位比較的算法思路編寫的算法代碼如下：
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
// 1.找出最短的字符串長度
int minLength = strs[0].length();
for (int i = 1; i < strs.length; i ++) {
if (minLength > strs[i].length()) {
minLength = strs[i].length();
}
}
if (minLength == 0) {
return "";
}
String prevStr = "";
for (int i = 0; i < minLength; i ++) {
char c = strs[0].charAt(i);
int j = 1;
for (; j < strs.length; j ++) {
if (c != strs[j].charAt(i)) { // 只需要比較相同位置的字符是否相等，若比較字符串時間復雜度會變高隐砸，效率降低
break;
}
}
if (j < strs.length) {
break;
}
prevStr = strs[0].substring(0, i + 1);
}
return prevStr;
}
根據(jù)水平掃描的算法思路編寫的算法代碼如下：
public String longestCommonPrefix(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 (i == strs[j].length() || c != strs[j].charAt(i)) {
return strs[0].substring(0, i);
}
}
}
return strs[0];
}
4.總結
這個算法有一點需要注意的是一定要比較相同位置上的字符之碗，而不是比較所有前綴都被字符串包含。
??如果你有疑問或更好的算法思路季希，歡迎留言交流Ｍ誓恰！式塌！
??如果感覺我的文章對您有所幫助博敬，麻煩動動小手給個喜歡，謝謝７宄ⅰＦ选！
