Longest Word in Dictionary through Deleting

Intuition

Solution

class Solution:
    def findLongestWord(self, s: str, d: List[str]) -> str:
        ans = []
        for word in d:
            if self.is_subsequence(s, word):
                ans.append(word)
        if not ans:
            return ""
        l = max([len(c) for c in ans])
        ans = [word for word in ans if len(word) == l]
        ans.sort()
        return ans[0]

    def is_subsequence(self, s, word):
        i = j = 0
        while i < len(s) and j < len(word):
            if s[i] == word[j]:
                i += 1
                j += 1
            else:
                i += 1
        return j == len(word)