# **Leetcode筆記(Longest Common Prefix)**

:::info
:information_source: 題目 : Longest Common Prefix, 類型 : string , 等級 : easy
日期 : 2023/05/11，2023/11/02
:::

### 嘗試
2023/11/02

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        res = ""

        for i in range(len(strs[0])):
            hub = strs[0][i]
            for s in strs:
                if i < len(s) and s[i] == hub:
                    continue
                else:
                    return res
            res += hub
        
        return res

---
### **優化**
用一個字先當基準，再用其他字當作比較對象，從最前端開始比較

最壞情況下的時間複雜度為 O(mn)，其中 m 是字符串中的平均字符數，n 是字符串的數量。
空間複雜度O(1)

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        
        res = ""

        for i in range(len(strs[0])):
            # 都會先試每個string的同個位置

            for s in strs[1:]:
                # 例如s為"flow"但strs[0]為"flower"
                # 到長度4就會報錯 而且也不用再找下去了
                # 另一個要回傳的情況是prefix不相同了
                if i >= len(s) or strs[0][i] != s[i]:
                    return strs[0][:i]

        # 處理如果只有單一個字串["a"]或是空[""]的情況
        return strs[0]        

---

**:warning: 錯誤語法**
:::warning

:::

**:thumbsup:學習**
:::success
Python支援的min()和max()，可以讓我們在List[str]中列出依字母排列順序最小和最大的字串
:::

**思路**

**講解連結**
https://www.youtube.com/watch?v=cGQez9SiScw&ab_channel=Michelle%E5%B0%8F%E6%A2%A6%E6%83%B3%E5%AE%B6
Provided by. Michelle小梦想家

###### tags: `string` `easy` `leetcode`