Longest Word in Dictionary through Deleting

自定义排序之后，利用子序列检查是一种很直觉的算法

class Solution(object):
    def findLongestWord(self, s, d):
        """
        :type s: str
        :type d: List[str]
        :rtype: str
        """
        def comparator(stringA, stringB):
            if len(stringA) != len(stringB):
                return cmp(len(stringB), len(stringA))
            return cmp(stringA, stringB)

        d.sort(cmp=comparator) 

        for string in d:
            if self.check(string, s):
                return string
        return ''

    def check(self, stringA, stringB):
        n, m = len(stringA), len(stringB)
        cur = 0
        for i in xrange(m):
            if stringB[i] == stringA[cur]:
                cur += 1
            if cur >= n:
                return True
        return False

时间复杂度O(nlgn），这里是不考虑字符串长度的时间复杂度

当然，如果不排序直接比较也是可以的，时间复杂度是O(n)，同样也是不考虑字符串的长度问题，方法比较trivial