力扣14 尋找字串陣列中最長公共前綴
題目：
撰寫一個函式來查找字串陣列中的最長公共前綴，
如果不存在公共前綴，回傳空字串 ""，
示例 1：
輸入：strs = ["flower","flow","flight"]
輸出："fl"
示例 2：
輸入：strs = ["dog","racecar","car"]
輸出：""
解釋：輸入不存在公共前綴，
提示：
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]僅由小寫英文字母組成
解題思路：
首先我們需要將這個字串陣列進行排序，然后找到這個字串陣列中最短的字串，因為進行回圈比較的時候比較的次數不會超過最短的字串的長度，進行排序后之后的陣列我們僅僅比較第一個字串與最后一個字串即可，
代碼：
import java.util.Arrays;
/**
* 回傳一個字串陣列中的最長的公共前綴，
* 首先我們可以對這個陣列進行排序,然后比較排序之后的第一個字串與最后一個字串
* 的元素是否相同,可以明確的是最多比較的次數是最短字串的長度
*/
public class MaxLengthSubStrings {
public static void main(String[] args) {
String[] strings = {"abc","abcd","abdsc","abcwsed"};
String s = maxLengthSubString(strings);
System.out.println("s = " + s);
}
//定義一個方法獲得最長的公共前綴,回傳值型別為String引數為String[] str
public static String maxLengthSubString(String[] str){
if (str == null || str.length == 0) {
return null;
}
if (str.length == 1) {
return str[0];
}
int len = str.length;
//對陣列進行排序
Arrays.sort(str);
String firstStr = str[0];
String lastStr = str[len - 1];
//定義一個StringBuilder用來接收最長的公共前綴
StringBuilder stringBuilder = new StringBuilder();
//取得字串陣列中的最短字串的長度
int minLength = Math.min(firstStr.length(),lastStr.length());
//判斷第一個字串與最后一個字串相同的字符
for (int i = 0; i < minLength; i++) {
if(firstStr.charAt(i) == lastStr.charAt(i)){
//如果字符相等就添加進stringBuilder
stringBuilder.append(firstStr.charAt(i));
}else {
//否則就退出比較
break;
}
}
return stringBuilder.toString();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/539442.html
標籤：其他
上一篇：C++入門級基礎知識匯總