最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • LeetCode第524题:通过删除字母匹配到字典里最长单词&最长子序列

    正文概述 掘金(奥奥奥)   2021-06-06   51

    题干

    给你一个字符串 s 和一个字符串数组 dictionary 作为字典,找出并返回字典中最长的字符串,该字符串可以通过删除 s 中的某些字符得到。

    如果答案不止一个,返回长度最长且字典序最小的字符串。如果答案不存在,则返回空字符串。

    实例:

    输入:s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
    输出:"apple"
    

    解法:双指针

    此题分为两部分,第一部分是在字典中寻找符合我们要求的元素,这一部分我是使用了双指针的做法,在每一次循环结束前将此次得到的结果,与上一个我们存储的目标值进行比较,长度长者胜出,留下,然后进行下一个对比,接下来就是第二部分,如果我们得到的目标值是相等的,那么就需要我们再次对于这两个字符串的字典序进行比较,然后返回字典序较小的值

    注意:这里的字典序不是ASCII码,准确来说是字母的顺序,比如"bab", ["ba", "ab", "a", "b"]就要返回ab,很明显对于这两个长度长度相同的字符串我们比较的是这两者的字母顺序。这里我采用的也是双指针的做法。

    代码:

    /**
     * @param {string} s
     * @param {string[]} dictionary
     * @return {string}
     */
      var findLongestWord = function (s, dictionary) {
            // 存储所有符合条件的tartget
            let targetStr = ''
            // 先遍历字典
            for (let i = 0; i < dictionary.length; i++) {
                // 分别定义预目标与两个指针变量,其中index1是s的指针,index2是预目标的指针
                let readyTarget = dictionary[i];
                let index1 = 0;
                let index2 = 0;
                while (index1 < s.length) {
                    if (s[index1] == readyTarget[index2]) {
                        index1++;
                        index2++;
                    } else {
                        index1++
                    }
                }
                // 符合条件比较,如果长度不等,则直接返回
                if (index2 == dictionary[i].length) {
                    if (targetStr.length < dictionary[i].length) {
                        targetStr = dictionary[i]
                    } else if (targetStr.length == dictionary[i].length) {
                            targetStr = GetStringNum(targetStr,dictionary[i])
                    }
                }
            }
            return targetStr
        };
        function GetStringNum(preString, nextString) {
            let index1 = 0, index2 = 0;
            let length = preString.length
            while (index1 < length || index2 < length) {
                if (preString[index1].charCodeAt()>nextString[index2].charCodeAt()) {
                    return nextString
                }else if(preString[index1].charCodeAt()<nextString[index2].charCodeAt()){
                    return preString
                }
                index1++;
                index2++;
            }
            return preString
        }
    

    起源地 » LeetCode第524题:通过删除字母匹配到字典里最长单词&最长子序列

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元