leetcode

leetcode 524题

Posted by franki on November 8, 2022

leetcode 524 通过删除字母匹配到字典里最长单词

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1

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

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

示例2

输入：s = "abpcplea", dictionary = ["a","b","c"]
输出："a"

思路

利用双指针，一个指向 dictory 下的每个单词的小标，一个指向 s 的下标，使用双循环，不断比较这两个下标对应的值，每一个 dictory[i] 遍历结束后，查看是否满足找到 s 的要求，如果满足则得到结果。

代码

/**
 * @param {string} s
 * @param {string[]} dictionary
 * @return {string}
 */
var findLongestWord = function(s, dictionary) {
    let res = '';

    function wordCompare(a, b) {
        let res1 = 0;
        for (const c of a.split('')) {
            res1 += c.charCodeAt();
        }

        let res2 = 0;
        for (const c of b.split('')) {
            res2 += c.charCodeAt();
        }

        return res1 > res2;
    }

    for (const t of dictionary) {
        let sIndex = 0;
        let dIndex = 0;

        while (sIndex < s.length && dIndex < t.length) {
            if (s[sIndex] === t[dIndex]) {
                dIndex++;
            }

            sIndex++;
        }

        if (dIndex === t.length) {
            if (res.length < t.length || (res.length === t.length && t < res)) {
                res = t;
            }
        }
    }

    return res;
};

复杂度分析:

  • 时间复杂度: O(N^2)
  • 空间复杂度：O(1)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG
    FRIENDS