美文网首页
leetcode算法-最长公共前缀

leetcode算法-最长公共前缀

作者: Weastsea | 来源:发表于2020-04-27 23:10 被阅读0次

    最长公共前缀

    编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""。

    示例 1:
    
    输入: ["flower","flow","flight"]
    输出: "fl"
    
    
    示例 2:
    
    输入: ["dog","racecar","car"]
    输出: ""
    解释: 输入不存在公共前缀。
    

    说明:
    所有输入只包含小写字母 a-z 。

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/longest-common-prefix
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    我就记录一下我的思路吧,没有特别复杂的技巧,特别的直,直来直去的。
    思路: 让我们计算公共的前缀,那么我的思路就是从前2个元素开始干起,循环比较,计算出前2个公共的前缀(此时并不一定就是所有元素的公共前缀),我们从第2个元素开始,与公共前缀进行比较,如果不一样,就把公共前缀从不一样的地方直接截取掉(更新公共前缀为截取后的),循环后面的所有元素,并且不断的去更新前缀,循环结束,直接返回最后的前缀。

    以下是代码实现,虽然繁碎,但是相信是比较容易理解的实现:

    var longestCommonPrefix = function (strs) {
        if (strs.length === 1) return strs[0]
        let pre = ''
        for (let i = 0; i < strs.length; i++) {
            const curS = strs[i]
            let j = 0
            let z = 0
            // 前2个的比较逻辑
            if (i === 0) {
                const nextS = strs[i + 1]
                while (j < curS.length) {
                    if (curS[j] === nextS[j]) {
                        pre += curS[j]
                    }
                    j++
                }
            } else {
                while (z < pre.length) {
                    // 此处多比较一次
                    if (pre[z] !== curS[z]) {
                        pre = pre.substring(0, z)
                        break
                    }
                    z++
                }
            }
        }
        return pre
    }
    

    相关文章

      网友评论

          本文标题:leetcode算法-最长公共前缀

          本文链接:https://www.haomeiwen.com/subject/hubpwhtx.html