[LeetCode] 14. Longest Common Prefix (JS)

[LeetCode] 14. Longest Common Prefix (JS)

題目

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

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
};
guest

0 評論
內聯回饋
查看全部評論