1190. Longest Word in Dictionary through Deleting

way 1: O(m*n) time.
字典按照要求排序, 长度 + 字典序.
对应每一个字典单词, 看看它是不是 s 的一个子序列.

Note. Python 字符串 iterator 用法. it = iter(s)
for c1 in it:
if c not in it:
省却了 next(it) 异常处理.

class Solution:
    def findLongestWord(self, s, d):
        # init
        for x in sorted(d, key=lambda x: (-len(x), x)):
            it = iter(s)
            is_lcs = False
            for c in x:
                is_lcs = False
                for c1 in it:
                    if c == c1:
                        is_lcs = True
                        break
            if is_lcs:
                return x
        return ''

class Solution:
    def findLongestWord(self, s, d):
        # init
        for x in sorted(d, key=lambda x: (-len(x), x)):
            it = iter(s)
            is_lcs = True
            for c in x:
                if c not in it:
                    is_lcs = False
                    continue
            if is_lcs:
                return x
        return ''

def findLongestWord(self, s, d):
    for x in sorted(d, key=lambda x: (-len(x), x)):
        it = iter(s)
        if all(c in it for c in x):
            return x
    return ''

s = "barfoofoobarthefoobarman"
d = ["xbar","foo","the"]

o = Solution()
ans = o.findLongestWord(s, d)
print(ans)