题目描述：

LeetCode 524. Longest Word in Dictionary through Deleting

Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:

Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output: 
"apple"

Example 2:

Input:
s = "abpcplea", d = ["a","b","c"]

Output: 
"a"

Note:

1. All the strings in the input will only contain lower-case letters.
2. The size of the dictionary won't exceed 1,000.
3. The length of all the strings in the input won't exceed 1,000.

题目大意：

给定字符串s和字典d，判断s删去一部分字符是否可以组成的d中的字符串。若可以，求长度最长且字典序最小的字符串。否则返回空串。

注意：

1. 所有字符串输入只包含小写字母。
2. 字典长度不超过1000。
3. 所有字符串长度不超过1000。

解题思路：

贪心算法 + 广度优先搜索

首先利用d中的各字符串w构造字典dmap：key为w中的字母，value为(i, w)；i初始为0，表示key在w中的下标。

然后遍历字符串s，记当前字符为c

  将dmap[c]取出，记为wlist

  遍历wlist，记当前元素为i, w

     若i + 1 == len(w)，表明w已经在s中匹配完成，将w加入结果集ans
     
     否则，将(i + 1, w) 加入 dmap[w[i + 1]]

最后返回ans中符合题设要求的字符串即可

Python代码：

class Solution(object):
    def findLongestWord(self, s, d):
        """
        :type s: str
        :type d: List[str]
        :rtype: str
        """
        ans = []
        dmap = collections.defaultdict(list)
        for w in d:
            dmap[w[0]].append((0, w))
        for c in s:
            wlist = dmap[c]
            del dmap[c]
            for i, w in wlist:
                if i + 1 == len(w):
                    ans.append(w)
                else:
                    dmap[w[i + 1]].append((i + 1, w))
        if not ans: return ''
        maxl = len(max(ans, key = len))
        return min(w for w in ans if len(w) == maxl)

 

本文链接：http://bookshadow.com/weblog/2017/02/26/leetcode-longest-word-in-dictionary-through-deleting/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码