LeetCode Js-14. Longest Common Prefix

    AllenLi
    LeetCode Js-String

    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 “”.

    判斷陣列的字串中，找出最長的共同字串，否則回傳空值。

    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.

    Solution:
    1. 先排除input不是字串的狀況(小優化)。(ex.傳入空值)
    2. 以陣列中第一組字串作為基準，互相比對字串是否連續相符。
    3. 如相符放入prefix陣列，不相符即回傳當前的prefix。

    Code 1:

    var longestCommonPrefix = function(strs) {
    if (!strs.length) return ""
    let prefix = ""
    for (let i = 0; i < strs[0].length; i++) {
        for (let j = 0; j < strs.length - 1; j++) {
            if (strs[j][i] !== strs[j+1][i]) return prefix;
        }
        prefix += strs[0][i]
    }
    return prefix
};

    FlowChart:
    Example 1

    let i=0, i<5; 
let j=0, j<2;

step1
strs[0][0] === strs[1][0] //['f'lower] = ['f'low] --->true
strs[1][0] === strs[2][0] //['f'low] = ['f'light] --->true
prefix += ['f']

step2
strs[0][1] === strs[1][1] //[f'l'ower] = [f'l'ow] --->true
strs[1][1] === strs[2][1] //[f'l'ow] = [f'l'ight] --->true
prefix += ['l']

step2
strs[0][2] === strs[1][2] //[fl'o'wer] = [fl'o'w] --->true
strs[1][2] === strs[2][2] //[fl'o'w] = [fl'i'ght] --->false
return prefix = ['fl']

    Example 2

    let i=0, i<3; 
let j=0, j<2;

step1
strs[0][0] !== strs[1][0] //['d'og] = ['r'acecar] --->false
return prefix = ['']

    Code 2:
    var longestCommonPrefix = function(strs) {
    if (!strs.length) return ""
    let prefix = ""
    let x = Math.min(...strs.map(o => o.length))

    for (let i = 0; i < x; i++) { let char = strs[0][i] if (strs.every(str => str[i] === char)){
    prefix += char
    } else {
    break
    }
    }
    return prefix
    };

    Related Posts