## 题目描述：

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.

## 题目大意：

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

## 解题思路：

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

将dmap[c]取出，记为wlist

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

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

否则，将(i + 1, w) 加入 dmap[w[i + 1]]

## 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)
``````

Pingbacks已关闭。