#14 Longest Common Prefix

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

LeetCode

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

• [] 空值

• ["", "", ""]

• 有一個值 ["a"] 那是印 a 還是 "" (印 "a"")

怎麼解

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

• 從最左邊開始找 (ind = 0)

  • 遍歷一輪看看所有 item[ind] 是不是一樣 while

  • 一樣的話 ind ++

  • 不一樣的話停止 return prefix

後來這樣改善

• 想處理 Edge Case

let len = strs.length;

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

• 比對前兩個字串，從頭開始取出相同的部分為共同字首

let same = strs[0];

• 後面的字串只要與目前的共同字首比對即可

• ['aab', 'aaa', 'ab', 'aa', aa] ，一開始'aab', 'aaa'共同字首前 2 碼'aa'

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

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