难度: Medium
给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。
示例 1：
输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"] 输出："apple"
示例 2：
输入：s = "abpcplea", dictionary = ["a","b","c"] 输出："a"
提示：
1 <= s.length <= 10001 <= dictionary.length <= 10001 <= dictionary[i].length <= 1000s 和 dictionary[i] 仅由小写英文字母组成运行时间: 48 ms
内存: 18.1 MB
class Solution:
def findLongestWord(self, s: str, dictionary: List[str]) -> str:
m = len(s)
# 可以想象为向后涂 26 个色带，第 i 位的字母会刷新该字母色带的颜色，其他字母不变
f = [[0] * 26 for _ in range(m)]
f.append([m] * 26)
for i in range(m - 1, -1, -1):
# 不变
for j in range(26):
f[i][j] = f[i + 1][j]
# 刷新
f[i][ord(s[i]) - 97] = i
res = ""
for t in dictionary:
j = 0
for c in t:
if f[j][ord(c) - 97] == m:
break
# 这里匹配之后进一位
j = f[j][ord(c) - 97] + 1
else:
# 如果没有break说明字母匹配了，执行此逻辑
if len(t) > len(res) or (len(t) == len(res) and t < res):
res = t
return res
该题解的思路是利用动态规划预处理字符串 s，为每个字符建立一个长度为 26 的数组，记录每个字母下一次出现的位置。然后对于字典中的每个单词，逐个字符在预处理数组中匹配，如果能够匹配到单词的所有字符，则说明该单词可以通过删除 s 中的某些字符得到。最后从所有匹配成功的单词中选择长度最长且字母序最小的单词作为答案。
时间复杂度: O(m + kn)
空间复杂度: O(m)
class Solution:
def findLongestWord(self, s: str, dictionary: List[str]) -> str:
m = len(s)
# 预处理字符串 s，为每个字符建立一个长度为 26 的数组，记录每个字母下一次出现的位置
f = [[0] * 26 for _ in range(m)]
f.append([m] * 26)
for i in range(m - 1, -1, -1):
# 其他字母位置不变
for j in range(26):
f[i][j] = f[i + 1][j]
# 刷新当前字母的下一次出现位置
f[i][ord(s[i]) - 97] = i
res = ""
for t in dictionary:
j = 0
for c in t:
if f[j][ord(c) - 97] == m:
break
# 匹配成功，移动到下一个字符的位置
j = f[j][ord(c) - 97] + 1
else:
# 如果匹配成功，更新答案
if len(t) > len(res) or (len(t) == len(res) and t < res):
res = t
return res
在预处理数组中添加一个长度为26的数组元素，且其每个位置的值都是m，是为了处理边界情况，即当某个字符在当前位置之后不再出现时。这样设置可以确保在使用预处理数组进行字符查找时，若当前字符在后续位置中不存在，数组会返回一个大于字符串s长度的值m，从而使得循环可以正常终止。这样的处理避免了额外的边界检查，简化代码逻辑。
通过预处理数组，每个字符位置记录了在字符串s中该字符下一次出现的位置。如果某个字符在s中不存在，对应的预处理数组的值将会是m（s的长度）。在遍历字典中的单词时，如果遇到某个字符在s中不存在，预处理数组会提供一个值m，这个值用于终止当前单词的匹配过程，因为它超出了s的范围。这保证了每次字符的查找都有效且能正确处理字符不存在的情况。
在Python中，`for-else`结构中的`else`部分会在`for`循环正常结束后执行，而不是因为`break`而中断时执行。这种结构在这里被用来检查是否每个字符都成功匹配到了s中的对应字符。如果所有字符都匹配成功（即没有触发`break`），则执行`else`子句中的代码来更新结果。这样的设计减少了额外的状态标志或检查，使得代码更为简洁和直观。
在确定最终结果的单词时，首先比较两个单词的长度，长度较长的单词优先。如果长度相同，则比较两个单词的字母序。在Python中，字符串的比较是按字典顺序进行的，因此，如果单词t的字母序小于当前结果res的字母序（即`t < res`），则t会替换res作为新的结果。这样的比较逻辑确保了在长度相同的情况下，字典序较小的单词被选择。