最長公共前綴(Java)

• 2022 年 10 月 11 日
• 筆記
• 力扣

編寫一個函數來查找字元串數組中的最長公共前綴。

如果不存在公共前綴，返回空字元串 ""。

示例 1：

輸入：strs = ["flower","flow","flight"]
輸出："fl"

示例 2：

輸入：strs = ["dog","racecar","car"]
輸出：""
解釋：輸入不存在公共前綴。

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 僅由小寫英文字母組成

思路分析：如果是個空數組，直接返回空字元串。以第一個字元串作為標準，分別與後面的每個字元串進行比較。

程式碼實現：

import java.util.Iterator;

//題目鏈接：//leetcode.cn/problems/longest-common-prefix/
public class T14 {

	public static void main(String[] args) {
		// 測試一把
		Solution solution = new Solution();
		String[] str = { "flower","flow","flowight"};
		String string = solution.longestCommonPrefix(str);
		System.out.println(string);
	}

}

class Solution {
	public String longestCommonPrefix(String[] strs) {
		if (strs.length == 0) {//如果是個空數組，直接返回空字元串
			return "";
		}
		String ans = strs[0];// 先把數組第一個字元串作為標準
		for (int i = 1; i < strs.length; i++) {// 分別與後面的字元串進行比較
			int j = 0;
			/**
			 *  int j = 0; => 這個寫在外面是為了後面能夠得到j的值,
			 *  從而得到在哪裡有公共前綴，如果寫在裡面，一旦跳出for循環，將無法得到
			 *  公共前綴的坐標
			 */
			for (; j < ans.length() && j < strs[i].length(); j++) {
				/**
				 * j < ans.length() && j < strs[i].length() => 比較的時候，總得
				 * 在兩個要比較的字元串的長度內進行比較，更準確的說，應該是在
				 * 兩個字元串中的較短的字元串長度內進行比較
				 */
			
				if (ans.charAt(j) != strs[i].charAt(j)) {
					//只要發現有一個字元不匹配，則立即跳出循環
					break;
				}
			}
			ans = ans.substring(0, j);//得到公共前綴
			/**
			 * substring(int beginIndex, int endIndex)方法的作用：
			 * 返回一個新字元串，它是此字元串的一個子字元串。
			 * 該子字元串從指定的 beginIndex 處開始，直到索引 endIndex - 1 處的字元。
			 * 因此，該子字元串的長度為 endIndex-beginIndex。 
			示例： 
			
			 "hamburger".substring(4, 8) returns "urge"
			 "smiles".substring(1, 5) returns "mile"

			 */
			if (ans.equals("")) {//如果發現沒有公共前綴，則返回空字元串
				return ans;
			}

		}
		return ans;//返回最終結果
	}
}

運行結果：