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

链接：524.通过删除字母匹配到字典里最长单词
难度：Medium
标签：数组、双指针、字符串、排序
简介：给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。

题解 1 - javascript

• 编辑时间：2021-09-14
• 执行用时：132ms
• 内存消耗：42.8MB
• 编程语言：javascript
• 解法介绍：双指针。

function findLongestWord(s: string, dictionary: string[]): string {
        const n = dictionary.length;
        const idxs = new Array(n).fill(0);
        for (const c of s) {
          for (let i = 0; i < n; i++) {
            if (dictionary[i][idxs[i]] === c) idxs[i]++;
          }
        }
        let ans!: string;
        for (let i = 0; i < n; i++) {
          if (dictionary[i].length === idxs[i]) {
            if (!ans) ans = dictionary[i];
            else ans = check(dictionary[i], ans);
          }
        }
        return ans ?? '';
        function check(str1: string, str2: string): string {
          const n1 = str1.length;
          const n2 = str2.length;
          if (n1 > n2) return str1;
          if (n1 < n2) return str2;
          let idx = 0;
          while (idx < n1) {
            if (str1[idx] !== str2[idx])
              return str1.codePointAt(idx)! > str2.codePointAt(idx)! ? str2 : str1;
            idx++;
          }
          return str1;
        }
      }