0524. 通过删除字母匹配到字典里最长单词【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 排序 + 子序列判定

1. 📝 题目描述

• leetcode

给你一个字符串 s 和一个字符串数组 dictionary，找出并返回 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] 仅由小写英文字母组成

2. 🎯 s.1 - 排序 + 子序列判定

c

int cmp(const void* a, const void* b) {
    const char* sa = *(const char**)a;
    const char* sb = *(const char**)b;
    int la = strlen(sa), lb = strlen(sb);
    if (la != lb) return lb - la;
    return strcmp(sa, sb);
}

char* findLongestWord(char* s, char** dictionary, int dictionarySize) {
    qsort(dictionary, dictionarySize, sizeof(char*), cmp);
    int sLen = strlen(s);
    for (int k = 0; k < dictionarySize; k++) {
        int i = 0, wLen = strlen(dictionary[k]);
        for (int j = 0; j < sLen && i < wLen; j++)
            if (s[j] == dictionary[k][i]) i++;
        if (i == wLen) return dictionary[k];
    }
    return "";
}

js

/**
 * @param {string} s
 * @param {string[]} dictionary
 * @return {string}
 */
var findLongestWord = function (s, dictionary) {
  dictionary.sort((a, b) => b.length - a.length || a.localeCompare(b))
  for (const word of dictionary) {
    let i = 0
    for (let j = 0; j < s.length && i < word.length; j++)
      if (s[j] === word[i]) i++
    if (i === word.length) return word
  }
  return ''
}

py

class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        dictionary.sort(key=lambda x: (-len(x), x))
        for word in dictionary:
            i = 0
            for ch in s:
                if i < len(word) and ch == word[i]:
                    i += 1
            if i == len(word):
                return word
        return ''

• 时间复杂度：$O(d\times (m\log m+n))$，其中 $d$ 是字典大小，$m$ 、$n$ 分别是单词和 $s$ 的长度
• 空间复杂度：$O(\log d)$（排序开销）

算法思路：

• 按长度降序、字典序升序排列字典
• 依次判断每个单词是否是 $s$ 的子序列，第一个匹配的即为答案