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删除了若干个字母而得到的，同时需要保证这个找到的单词的字典序最小。

思路是双指针，类似于392题找子序列。因为S删除字母是无序的，所以只能通过判断子序列的方式来看d中的每个单词是不是由S而来。如果你找到一个单词了，之后再有一个单词，他也是S的子序列的时候，需要用str.compareTo()额外判断str的字典序是否比res小，若是则替换res，从而得到字典序最小的结果。

时间O(n^2)

空间O(1)

Java实现

 1 class Solution {
 2     public String findLongestWord(String s, List<String> d) {
 3         String res = "";
 4         for (String str : d) {
 5             if (isSubsequence(str, s)) {
 6                 if (str.length() > res.length() || (str.length() == res.length() && str.compareTo(res) < 0)) {
 7                     res = str;
 8                 }
 9             }
10         }
11         return res;
12     }
13 
14     private boolean isSubsequence(String s, String t) {
15         if (s == null || s.length() == 0) {
16             return true;
17         }
18         int i = 0;
19         int j = 0;
20         while (i < s.length() && j < t.length()) {
21             if (s.charAt(i) == t.charAt(j)) {
22                 i++;
23             }
24             j++;
25         }
26         return i == s.length();
27     }
28 }

 

相关题目

392. Is Subsequence

524. Longest Word in Dictionary through Deleting

LeetCode 题目总结