Leetcode524.通过删除字母匹配到字典里最长单词

题目描述：

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

示例1：

输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
输出:
"apple"

示例2：

输入:
s = "abpcplea", d = ["a","b","c"]
输出:
"a"

说明:

所有输入的字符串只包含小写字母。
字典的大小不会超过 1000。
所有输入的字符串长度不会超过 1000。

解答思路一：按顺序进行索引，切片，找到匹配的字符串

class Solution(object):
    def findLongestWord(self, s, d):
        """
        :type s: str
        :type d: List[str]
        :rtype: str
        """
        max = float('-inf')
        result = ''
        source = s
        for string in d:
            i = 0
            while i < len(string):
                if string[i] in s:
                    try:
                        s = s[s.index(string[i])+1:]
                    except IndexError:
                        s = ''
                    finally:
                        i += 1
                else:
                    break
            if i == len(string):
                if len(string) > max:
                    max = len(string)
                    result = string
                elif len(string) == max:
                    result = result if result < string else string
                else:
                    pass
            s = source
        return result

解答思路二：排序，然后找到匹配值

class Solution(object):
    def findLongestWord(self, s, d):
        """
        :type s: str
        :type d: List[str]
        :rtype: str
        """
        # 先将d中的单词按照长度由长到短排序，再按照字母顺序，从小到大
        d.sort(key=lambda x: (-len(x), x))
        
        # 然后依次比较d中字符串与字典s，如果出现匹配就直接返回
        for word in d:
            i = 0
            for l in s:
                if l == word[i]:
                    i += 1
                if i == len(word):
                    return word
        return ''