【Leetcode】【Easy】14. Longest Common Prefix 解題
題目
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: strs = ["flower","flow","flight"] Output: "fl"
Example 2:
Input: strs = ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.
Constraints:
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]consists of only lowercase English letters.
解答
- 截取第一個 String 的 Prefix，如果都有相同的前綴，則繼續截取
- 跑一個 for 迴圈，比對每個字串是否都有相同的前綴
- 計算相同前綴的次數
- 如果相同前綴次數 = String Array 的 String 個數，把舊 Prefix 替換成新 Prefix
- 如果沒有相同 Prefix 或截取的 Prefix 次數 <= 第一個 String 的長度則中斷迴圈
public static String longestCommonPrefix(String[] strs) {
boolean hasCommonPrefix;
int subStringCounts = 1; // 從 x 截取字串
String firstStr = strs[0]; // 取得 String Array 第一個字串
String commonPrefix = ""; // 相同前綴
if (!firstStr.isEmpty()) {
while (true) {
String prefix = firstStr.substring(0, subStringCounts); // 前綴
int commonPrefixCounts = 0; // 相同前綴次數
for (String str : strs) {
// 比對 String Array 的每個 String 是否有相同前綴
if (subStringCounts <= str.length()) {
String tempSubString = str.substring(0, subStringCounts);
boolean contains = tempSubString.equals(prefix);
if (contains) {
commonPrefixCounts++;
}
}
}
if (commonPrefixCounts == strs.length) {
// 如果相同次數 = String Array 的 String 個數，把舊 Prefix 替換成新 Prefix
commonPrefix = prefix;
hasCommonPrefix = true;
} else {
hasCommonPrefix = false;
}
if (!hasCommonPrefix || subStringCounts == firstStr.length()) {
break;
}
subStringCounts++;
}
}
return commonPrefix;
}
