[LeetCode] 14. Longest Common Prefix (JS)

3 個月前

內容目錄 隱藏

題目

編寫一個函數來尋找字串陣列中最長的共同前綴字串。如果沒有共同前綴，則傳回空字串 "" 。

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.

Constraints:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters.

解題思路

需要考慮三種情況：

空陣列：直接回傳空字串
只有一個元素：直接回傳該元素
多個元素：檢查當前字串 strs[i] 是否以當前前綴 prefix 開頭，如果不是就縮短前綴，直到找到共同前綴或前綴變成空字串。prefix 預設為第一個元素字串。

完整程式碼

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return ''
    if (strs.length === 1) return strs[0]
    
    let prefix = strs[0]
    
    for (let i = 1; i < strs.length; i++) {
        // 檢查當前字串 strs[i] 是否以當前前綴 prefix 開頭
        // 如果不是就縮短前綴，直到找到共同前綴或者前綴變成空字串
        while (strs[i].indexOf(prefix) !== 0) {
            prefix = prefix.slice(0, -1)
            if (prefix === '') return ''
        }
    }
    return prefix
};