---
# System prepended metadata

title: 14. Longest Common Prefix
tags: [LeetCode]

---

# 14. Longest Common Prefix
### 題目: 最長公共前綴
給你一個字符串數組 strs，找出其中所有字符串的最長公共前綴。如果不存在公共前綴，返回空字符串 ""。


---

### 範例1:
```
輸入: strs = ["flower", "flow", "flight"]
輸出: "fl"
解釋: 所有字符串的最長公共前綴是 "fl"。
```
### 範例2:
```
輸入: strs = ["dog", "racecar", "car"]
輸出: ""
解釋: 輸入中的字符串沒有公共前綴，所以結果為空字符串 ""。
```


---

### 提示
* 前綴概念：你需要找出所有字符串中都存在的最長前綴。從第一个字符串的前缀开始，逐步缩短前缀长度，直到找到一个所有字符串的公共前缀。

* 逐步比較：逐個比較字符串的前綴，從第一个字符串的前缀开始，與其他字符串的前缀進行比對。當發現不匹配時，縮短前缀長度。

* 退出條件：當最長前缀變為空字符串時，表示沒有公共前缀，應立即返回空字符串。


---

### 解答
我的版本:
```
public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        
        string prefix = strs[0];
        for(int i = 1; i < strs.Length; i++){

            while(strs[i].IndexOf(prefix) != 0){
                prefix = prefix.Substring(0, prefix.Length - 1);
            }

            if(prefix.Length == 0){
                return "";
            }
        }
        return prefix;
    }
}
```
[leetcode的大神](https://leetcode.com/problems/longest-common-prefix/solutions/4711312/simple-and-easy-solution-in-java-python-c-c/)
```
public class Solution {
    // Intuition: The idea is to iterate through each character position in the first string
    // and compare it with the corresponding characters in the other strings.
    
    // Approach: Use nested loops to iterate through characters in the first string
    // and compare with the corresponding characters in the rest of the strings.
    // If a mismatch is found or if the index goes beyond the length of any string, return the current prefix.
    public string LongestCommonPrefix(string[] strs) {
        // Initialize an empty string to store the longest common prefix.
        string s = "";
        
        // Iterate through each character position in the first string (strs[0]).
        for (int i = 0; i < strs[0].Length; i++) {
            // Iterate through the other strings starting from index 1.
            for (int j = 1; j < strs.Length; j++) {
                // Check if the current index i is out of bounds for the current string (strs[j])
                // or if the characters at position i are different between strs[j] and strs[0].
                if (i >= strs[j].Length || strs[j][i] != strs[0][i]) {
                    // Return the current prefix as the result.
                    return s;
                }
            }
            // Append the current character to the common prefix.
            s += strs[0][i];
        }
        
        // Return the final common prefix.
        return s;
    }
}
```
