0524：通过删除字母匹配到字典里最长单词（★）

2016-06-07 约 369 字预计阅读 1 分钟次阅读

力扣第 524 题

题目

给你一个字符串 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] 仅由小写英文字母组成

相似问题：

0720：词典中最长的单词

分析

遍历判断是否子序列即可。

解答

1
2
3
4
5
6
7
8


class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        res = ''
        for t in dictionary:
            it = iter(s)
            if all(c in it for c in t) and (-len(t),t)<(-len(res),res):
                res = t
        return res

90 ms

*附加

还可以预处理 s 的序列自动机，节省子序列判断时间。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        def check(t):
            i = 0
            for c in t:
                if c not in f[i]:
                    return False
                i = f[i][c]+1
            return True

        n = len(s)
        f = [{} for _ in range(n+1)]
        for i in range(n-1,-1,-1):
            f[i] = f[i+1].copy()
            f[i][s[i]] = i
        res = ''
        for t in dictionary:
            if check(t) and (-len(t),t)<(-len(res),res):
                res = t
        return res

56 ms

目录

0524：通过删除字母匹配到字典里最长单词（★）

题目

分析

解答

*附加