#14 Longest Common Prefix

startsWith 請把邏輯寫在紙上會更清楚，因為直接寫 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 

f

/**
 * @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
};