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

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

给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。
​

示例 1：
输入：s = “abpcplea”, dictionary = [“ale”,”apple”,”monkey”,”plea”] 输出：”apple”
示例 2：
输入：s = “abpcplea”, dictionary = [“a”,”b”,”c”] 输出：”a”
​

提示：

• 1 <= s.length <= 1000
• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 1000
• s 和 dictionary[i] 仅由小写英文字母组成

思路

双指针，判断当前单词是否能通过 s 删除得到，可以的话再根据 max 判断是否要更新当前单词，如果相同通过字典序来比较更新。

解答

/**
 * @param {string} s
 * @param {string[]} dictionary
 * @return {string}
 */
var findLongestWord = function (s, dictionary) {
  let max = -Infinity,
    res = "";
  for (const word of dictionary) {
    let i = 0,
      j = 0;
    while (i < s.length && j < word.length) {
      if (s[i++] === word[j]) j++;
    }
    if (j === word.length) {
      if (word.length > max) {
        max = word.length;
        res = word;
      } else if (word.length === max) {
        res = word > res ? res : word;
      }
    }
  }
  return res;
};