問(wèn)題
Write a function to find the longest common prefix string amongst an array of strings.
大意：
寫一個(gè)函數(shù)來(lái)尋找一個(gè)數(shù)組的字符串中最長(zhǎng)的相同前綴理张。
思路：
題目描述很簡(jiǎn)單只有一句話冈欢，導(dǎo)致我理解錯(cuò)了，以為是找到存在的任意兩個(gè)字符串最長(zhǎng)的相同前綴犀勒，還寫了一份代碼出來(lái)，自己測(cè)試的時(shí)候發(fā)現(xiàn)題目想要的結(jié)果不符合才發(fā)現(xiàn)侠仇，其實(shí)是找整個(gè)數(shù)組的字符串都有的相同的最長(zhǎng)前綴磕秤，這就方便多了。
我采用從第一個(gè)字符串的前頭開始一個(gè)一個(gè)地增加前綴長(zhǎng)度來(lái)判斷后面所有的字符串是否有同樣的前綴臭笆，然后返回結(jié)果叙淌。
在這個(gè)過(guò)程中有很多特殊情況要注意秤掌，比如如果數(shù)組長(zhǎng)度為0，直接返回空字符串鹰霍；如果只有一個(gè)字符串闻鉴，直接返回該字符串；如果存在某個(gè)字符串（包括第一個(gè)）就是“”這樣的空字符串茂洒，直接返回“”孟岛；每次增加前綴長(zhǎng)度的時(shí)候要判斷第一個(gè)字符串是否夠長(zhǎng)，不夠了就直接返回當(dāng)前結(jié)果获黔；只有當(dāng)所有后面的字符串都存在前綴時(shí)才可以認(rèn)為是相同的蚀苛，只要有一個(gè)不相同就可以直接返回之前已經(jīng)記錄的前綴了等等。
代碼（Java）：
public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
else if (strs.length == 1) return strs[0];
int end = 1;
String result = "";
String firstStr = strs[0];
if (firstStr.length() == 0) return "";
else {
String sub;
while (end <= firstStr.length()) {
sub = firstStr.substring(0, end);
for (int i = 1; i < strs.length; i++) {
String nowStr = strs[i];
if (nowStr.length() == 0) return "";
else {
if (nowStr.startsWith(sub, 0)) {
if (i == strs.length-1) {
result = sub;
end ++;
}
} else return result;
}
}
}
}
return result;
}
}
他山之石：
public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
String pre = strs[0];
for (int i = 1; i < strs.length; i++)
while(strs[i].indexOf(pre) != 0) {
pre = pre.substring(0,pre.length()-1);
if (pre.length() == 0) return "";
}
return pre;
}
}
這個(gè)做法是先用整個(gè)第一個(gè)字符串來(lái)當(dāng)做前綴去判斷每個(gè)字符串是否擁有該前綴玷氏，沒(méi)有就將這個(gè)判斷的前綴末尾字符去掉再比較堵未，直到當(dāng)前判斷的字符串有這個(gè)前綴了，才去判斷下一個(gè)字符串有沒(méi)有盏触，執(zhí)行同樣的操作渗蟹。當(dāng)任何時(shí)候前綴長(zhǎng)度減少到0了，也可以直接返回了赞辩。這個(gè)做法會(huì)快一點(diǎn)雌芽，而且免去了很多特殊情況的判斷，代碼很簡(jiǎn)潔辨嗽。
合集：https://github.com/Cloudox/LeetCode-Record
