題目資訊
源地址：最長公共前綴
撰寫一個函式來查找字串陣列中的最長公共前綴，
如果不存在公共前綴，回傳空字串 ""，
提示資訊
示例 1
輸入：strs = ["flower","flow","flight"]
輸出："fl"
提示 2
輸入：strs = ["dog","racecar","car"]
輸出：""
解釋：輸入不存在公共前綴，
提示
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]僅由小寫英文字母組成
實作邏輯
逐一對比
此方法如其名稱，即將陣列中的字串逐一進行對比，先找出第一、第二個字串的最長公共前綴，再找出第二、第三個字串的最長公共前綴，以此類推，直至完成所有字串的比較，
當然，當在對比程序中發現最長公共前綴已經為空，則直接回傳即可，
此方式是較為常規的思路，時間復雜度為 \(O(mn)\)，其中 m 是字串陣列中字串的平均長度，n 是字串陣列的長度，最壞情況下，字串陣列中的每個字串都會被比較一次，
根據代碼的寫法不同，若利用額外的空間則空間復雜度是 \(O(n)\)，若使用陣列中的第一個字串做相關增減，則空間復雜度是 \(O(1)\)，
package cn.fatedeity.algorithm.leetcode;
public class LongestCommonPrefix {
public String answer(String[] strs) {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < strs.length; i++) {
if (stringBuilder.length() > strs[i].length()) {
stringBuilder.setLength(strs[i].length());
}
for (int j = 0; j < strs[i].length(); j++) {
char c = strs[i].charAt(j);
if (i == 0) {
stringBuilder.append(c);
continue;
} else if (stringBuilder.charAt(j) != c) {
stringBuilder.replace(j, stringBuilder.length(), "");
}
if (j >= stringBuilder.length() - 1) {
break;
}
}
if (stringBuilder.isEmpty()) {
return stringBuilder.toString();
}
}
return stringBuilder.toString();
}
}
同時對比
同時對比指的是，每一次對比的時候，都將陣列中所有的字串拿出來進行比較，如同時比較陣列中所有字串的第一個字符，然后比較陣列中所有字串的第二個字符，以此類推，直到已對比完整個字串，或者所在位置的字符有所不同，
此方法也是常規思路中的一種，時間復雜度為 \(O(mn)\)，其中 m 是字串陣列中字串的最小長度，n 是字串陣列的長度，最壞情況下，字串陣列中的每個字串都會被比較一次，
空間復雜度同逐一對比方法一樣，最低可以做到 \(O(1)\) 的空間復雜度，
package cn.fatedeity.algorithm.leetcode;
public class LongestCommonPrefix {
public String answer(String[] strs) {
StringBuilder commonStr = new StringBuilder(strs[0]);
if (strs.length == 1) {
return strs[0];
}
for (int i = 0; i < strs[0].length(); i++) {
for (int j = 1; j < strs.length; j++) {
if (strs[j].length() == i || commonStr.charAt(i) != strs[j].charAt(i)) {
commonStr.replace(i, commonStr.length(), "");
return commonStr.toString();
}
}
}
return commonStr.toString();
}
}
逐一對比優化
這里是一個優化的逐一對比方法，其實也是使用了編程語言的一些特性，直接判斷當前的公共前綴是否是下一個字串的公共前綴，只有滿足所有字串要求的前綴才是最終結果，
實際落實到代碼中就是，沒有自己將字串的每一個字符都做比較，而是使用編程代碼中已有的方法做比較，實際的時間復雜度沒有脫離 \(O(mn)\) 的范疇，但實際效果比自行開發的比較要好，
package cn.fatedeity.algorithm.leetcode;
public class LongestCommonPrefix {
public String answer(String[] strs) {
if (strs.length == 1) {
return strs[0];
}
String prefix = strs[0];
for (String str : strs) {
while (!str.startsWith(prefix)) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.length() == 0) {
return "";
}
}
}
return prefix;
}
}
首發于翔仔的個人博客，點擊查看更多，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/501719.html
標籤：其他