524. 通過删除字母比對到字典裡最長單詞

第一判斷 seq in dictionary 是否是 s 的子序列；

第二傳回最長且字典序最小的字元串。

方法一：雙指針

class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        res = ""
        for seq in dictionary:
            i = j = 0
            while i < len(seq) and j < len(s):
                if seq[i] == s[j]:
                    i += 1
                j += 1
            if i == len(seq):
                if len(seq) > len(res) or (len(seq) == len(res) and seq < res):
                    res = seq
        return res
           

方法二：find

class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        res = ''
        for seq in dictionary:
            idx = -1
            for ch in seq:
                idx = s.find(ch,idx+1)               
                if idx == -1:
                    break
            else:
                if len(seq) > len(res) or (len(seq) == len(res) and seq < res):
                    res = seq       
               
        return res
           

方法三：排序優化第二個問題

将 dictionary 依據字元串長度的降序和字典序的升序進行排序，然後從前向後找到第一個符合條件的字元串直接傳回即可。

class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        dictionary.sort(key=lambda x: (-len(x), x))
        for seq in dictionary:
            idx = -1
            for ch in seq:
                idx = s.find(ch,idx+1)               
                if idx == -1:
                    break
            else:
                return seq
        return ""
           

方法四：動态規劃

預處理字元串 s 優化第 1 個問題。

令 f [ i ] [ j ] f[i][j] f[i][j] 表示字元串 s 中從位置 i 開始往後字元 j 第一次出現的位置。在進行狀态轉移時，如果 s 中位置 i 的字元就是 j，那麼 f [ i ] [ j ] = i f[i][j]=i f[i][j]=i，否則 j 出現在位置 i+1 開始往後，即 f [ i ] [ j ] = f [ i + 1 ] [ j ] f[i][j]=f[i+1][j] f[i][j]=f[i+1][j]；是以我們要倒過來進行動态規劃，從後往前枚舉 i。

狀态轉移方程：

f [ i ] [ j ] = { i , s [ i ] = j f [ i + 1 ] [ j ] , s [ i ] ≠ j f[i][j]= \begin{cases} i, & s[i]=j \\ f[i+1][j], & s[i] \ne j \end{cases} f[i][j]={i,f[i+1][j],​s[i]=js[i]​=j​

假定下标從 0 開始，那麼 f [ i ] [ j ] f[i][j] f[i][j] 中有 0 ≤ i ≤ m − 1 0 \leq i \leq m-1 0≤i≤m−1 ，對于邊界狀态 f [ m − 1 ] [ . . ] f[m-1][..] f[m−1][..]，我們置 f [ m ] [ . . ] f[m][..] f[m][..] 為 m，讓 f [ m − 1 ] [ . . ] f[m-1][..] f[m−1][..] 正常進行轉移。這樣如果 f [ i ] [ j ] = m f[i][j]=m f[i][j]=m，則表示從位置 i 開始往後不存在字元 j。

這樣，利用 f 數組，每次 O(1) 地跳轉到下一個位置，直到位置變為 m 或 t 中的每一個字元都比對成功。

class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        m = len(s)
        f = [[0] * 26 for _ in range(m)]
        f.append([m] * 26)

        for i in range(m - 1, -1, -1):
            for j in range(26):
                if ord(s[i]) == j + 97:
                    f[i][j] = i
                else:
                    f[i][j] = f[i + 1][j]

        res = ""
        for t in dictionary:
            match = True
            j = 0
            for i in range(len(t)):
                if f[j][ord(t[i]) - 97] == m:
                    match = False
                    break
                j = f[j][ord(t[i]) - 97] + 1
            if match:
                if len(t) > len(res) or (len(t) == len(res) and t < res):
                    res = t
        return res