---
description: startsWith 請把邏輯寫在紙上會更清楚，因為直接寫 code 思考會常常亂掉 / 這題 Edge Case 很多，值得再寫一次
---

# #14 Longest Common Prefix

再[LeetCode](https://leetcode.com/problems/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 "".

input: 給一字串陣列
output: 找出他們共同 prefix，沒有的話就回傳空字串 ""
```

```
Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:

All given inputs are in lowercase letters a-z.
*/



// Edge Case []
// 只有一個值 ["a"] 那是印 a 還是 ""  (印 "a"")
/**
 * @param {string[]} strs
 * @return {string}
 */
// var longestCommonPrefix = function(strs) {
```

### Edge Case

* \[] 空值&#x20;
* \["", "", ""]
* 有一個值 \["a"] 那是印 a 還是 ""    (印 "a"")

### 怎麼解

本來是這樣想結果整個思緒亂掉

*   從最左邊開始找 (ind = 0)&#x20;

    * 遍歷一輪看看所有 item\[ind] 是不是一樣 while&#x20;
    * 一樣的話 ind ++&#x20;
    * 不一樣的話停止 return prefix



後來這樣改善

* 想處理 Edge Case

```
let len = strs.length;

if(len == 0){
    return ""
}else if(len == 1){
    return strs[0];
}
```

* 比對前兩個字串，從頭開始取出相同的部分為共同字首&#x20;

![](https://1787585077-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LqirD3iAZIDk4oDCfwS%2F-LrMJ04CapCqCOi81sGb%2F-LrMJvHvbkamsrWgwf83%2F1.jpg?alt=media\&token=db2f60c6-99aa-4778-a290-ecf8de36bb93)

```
let same = strs[0];
```

* 後面的字串只要與目前的共同字首比對即可
* \['aab', 'aaa', 'ab', 'aa', aa] ，一開始'aab', 'aaa'共同字首前 2 碼'aa'

![](https://1787585077-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LqirD3iAZIDk4oDCfwS%2F-LrMKNcqCUCXYZujlDxJ%2F-LrMKakU4w7QwJ4Mn-yV%2F2.jpg?alt=media\&token=8ae9d03b-7673-4650-9a72-ae3142c41f5f)

* 接下來只要將'aa',  'ab'做比對，發現剩下'a'，也就是最長的共同字首

![](https://1787585077-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LqirD3iAZIDk4oDCfwS%2F-LrMKNcqCUCXYZujlDxJ%2F-LrMKqxyDcn8ualOfMH9%2F3.jpg?alt=media\&token=d6d55ef4-6634-407a-b5e3-02740f1e34d2)

```
for(let i = 1; i< len; i++){
        let str = strs[i];

        // 取目前的字串 str 跟 same 相等的部分做為新的 same
        let j = 0;
        for(j ; j < same.length ; j++){
            if(same[j] != str.charAt(j)){
                 break;
            } 
         }

         same = same.slice(0, j);
    }
    return same;
```

### 完整程式碼

```
var longestCommonPrefix = function(strs) {
    let len = strs.length;
    // Edge Case
    if(len == 0){
        return ""
    }else if(len == 1){
        return strs[0];
    }
    
    // same 先等於第一個字串
    let same = strs[0];

    for(let i = 1; i< len; i++){
        let str = strs[i];

        // 取目前的字串 str 跟 same 相等的部分做為新的 same
        let j = 0;
        for(j ; j < same.length ; j++){
            if(same[j] != str.charAt(j)){
                 break;
            } 
         }

         same = same.slice(0, j);
    }
    return same;
}
console.log(longestCommonPrefix(["aab","aaa","ab","aa","aa"]))
// faster than 79.67% of JavaScript online submissions 
```

f

```javascript
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if(strs.length === 1) return strs[0]
    
    
    //["flower","flow"]
    function getCommonPrefix(aStr, bStr) {
        let len = Math.min(aStr.length, bStr.length)
        let i = 0;
        let prefix = ""
        
        while( i< len ){
            if(aStr[i] !== bStr[i]){
                return prefix
            }
            prefix += aStr[i]
            i++  
        }
        return prefix
    }
    
    let prefix = getCommonPrefix(strs[0], strs[1])  // "flow"
    for(let i=2;i< strs.length; i++){
        prefix = getCommonPrefix(prefix, strs[i])
    }
    
    return prefix
    
    
};
```

更好解法

```
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
  let prefix = strs[0]
  let i =1
  while(i<strs.length){
    if(!strs[i].startsWith(prefix)){
        prefix = prefix.slice(0, -1)
    } else {
        i++
    }
  }
  return prefix
};
```
