leetcode_14 最长公共子序列

1、暴力破解：循环数组，每一次比对当前元素和结果更新前缀

var longestCommonPrefix = function(strs) {
    if(strs.length <1) return ''
    let result = strs[0]
    let length = result.length
    for(let item of strs) {
        if(length===0) return ''
        if(result !== item.slice(0, length)) {
            for(let j=length; j>=0; j--){
                if(result.slice(0,j)===item.slice(0,j)){
                    result = item.slice(0,j)
                    length = j 
                    break
                }
            }
        } 
    }  
    return result         
};

2、归并求解，求所有子串的公共前缀，分解为两两求解，事实证明 更慢了。

var longestCommonPrefix = function(strs) {
    if(strs.length<1) return ''
    if(strs.length===1) return strs[0]
    let middle = Math.floor(strs.length/2)
    let left = strs.slice(0, middle)     
    let right = strs.slice(middle)
    return  commonTwo(longestCommonPrefix(left), longestCommonPrefix(right))
};
function commonTwo(left, right) {
    let length = left.length
    for(let j=length; j>=0; j--){
        if(left.slice(0,j)===right.slice(0,j)){
            return left.slice(0, j)
        }
    }
}