524 通过删除字母匹配到字典里最长单词（判断一个序列是否是另外一个序列的子序列）

╰半夏微凉° 2022-08-30 05:25 131阅读 0赞

**1. 问题描述：**

给你一个字符串 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\] 仅由小写英文字母组成  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting

**2. 思路分析：**

分析题目可以知道我们需要判断中字典中的字符串是否是另外一个字符串s的子序列，判断一个序列是否是另外一个字符串的子序列可以**双指针算法**，我们直接在循环中模拟一遍，依次判断字典中的每一个字符串是否是s的子序列即可。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        def check(self, a: str, b: str):
            k = 0
            for i in range(len(b)):
                if k < len(a) and a[k] == b[i]: k += 1
            return k == len(a)
    
        def findLongestWord(self, s: str, d: List[str]) -> str:
            res = ""
            for w in d:
                # 满足当前的字符串是s的子序列之后判断是否长度更长或者是长度相等但是字典序更小
                if self.check(w, s):
                    if not res or len(w) > len(res):
                        res = w
                    elif len(w) == len(res) and w < res:
                        res = w
            return res