Leetcode 14. 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 "".

找出在string陣列中自首最長且出現最頻繁的字串。如果沒有,則顯示空字串。

Example 1:

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

Example 2:

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

先來個暴力解,遍尋第一個字如果都一樣,則往下一個,假設第一個字沒有一樣,則空字串。

// 遍尋每個字串第一個字,如果都等於則放進ans。如果有不等於,就直接return ans

// 遍尋每個字串第二個字,剩下步驟同上

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    let ans = '';
    
    if(strs.length == 0) return '';
    if(strs.length == 1) return strs[0];
    
    for(let j = 0 ; j < strs[0].length; j++){
        let checkChat = '';
        let times = strs.length-1;
        for(let i = 0 ; i < strs.length ; i++){

            if(checkChat.length == 0){
                checkChat = strs[i][j]
                times--;
            }else{
                console.log(checkChat, strs[i][j])
                if(checkChat == strs[i][j]){
                    console.log('same',times)
                    if(times == 0){
                       ans = ans + checkChat
                    }else{
                        times--;
                    }

                }else{
                    return ans;
                }
            }
        }
    }
    return ans;
};

這樣的結果為O(pre.length*N)。這麼做的缺點為每次都要掃過一次相同位置的字元。

Leave a Comment

發佈留言必須填寫的電子郵件地址不會公開。