1.题目基本信息

1.1.题目描述

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

1.2.题目地址

https://leetcode.cn/problems/longest-word-in-dictionary-through-deleting/description/

2.解题方法

2.1.解题思路

双指针 / 动态规划

2.2.解题步骤

思路1：双指针

• 第一步，构建函数isSubStr判断s1是否是t的子序列

• 第二步，遍历，依次进行判断

思路2：动态规划

• 第一步，状态定义。dp[i][j]表示s中从下标i开始第一次出现字符j的位置（子序列自动机）

• 第二步，状态初始化。dp[*]=n表示暂时还没找到，dp[n-1][s[n-1]]=n-1

• 第三步，状态转移。dp[i][j]=dp[i+1][j] if s[i]!=j else i

• 第四步，根据s的dp数组，加速子序列匹配，遍历dictionary进行计算

3.解题代码

python3代码-双指针

class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        # 思路1：双指针
        # 第一步，构建函数isSubStr判断s1是否是t的子序列
        def isSubStr(s1:str, t:str) -> bool:
            i = 0
            for c in t:
                if s1[i] == c:
                    i += 1
                    if i == len(s1):
                        return True
            return False
        # 第二步，遍历，依次进行判断
        maxLen = 0
        result = ""
        for word in dictionary:
            if isSubStr(word, s):
                if len(word) > maxLen:
                    maxLen = len(word)
                    result = word
                elif len(word) == maxLen and word < result:
                    result = word
        return result

python3代码-动态规划

class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        # 思路2：动态规划
        n = len(s)
        # 第一步，状态定义。dp[i][j]表示s中从下标i开始第一次出现字符j的位置（子序列自动机）
        dp = [[n] * 26 for _ in range(n + 1)]
        # 第二步，状态初始化。dp[*]=n表示暂时还没找到，dp[n-1][s[n-1]]=n-1
        dp[n - 1][ord(s[n - 1]) - 97] = n - 1
        # 第三步，状态转移。dp[i][j]=dp[i+1][j] if s[i]!=j else i
        for i in range(n - 2, -1, -1):
            for j in range(26):
                dp[i][j] = dp[i + 1][j] if s[i] != chr(j + 97) else i
        # print(dp)
        # 第四步，根据s的dp数组，加速子序列匹配，遍历dictionary进行计算
        result = ""
        maxLen = 0
        for word in dictionary:
            ok = True   # word是否是s的子序列
            i = 0
            for ch in word:
                if dp[i][ord(ch) - 97] == n:
                    ok = False
                    break
                else:
                    i = dp[i][ord(ch) - 97] + 1 # 这里让i指向下一个开始匹配的位置，注意不是已经匹配的位置，所以需要加1
            if ok:
                if len(word) > maxLen or (len(word) == maxLen and word < result):
                    result = word
                    maxLen = len(word)
        return result

4.执行结果