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:

1
2
3
4
5
Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
Output: 
"apple"

Example 2:

1
2
3
4
5
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.

思路

错了很多次，都是因为边界条件的锅。

首先需要判断字符串的长度是否为0，如果为0就需要返回一个空的字符串——没有找到符合要求的字符串也需要返回空。

接下来，就是利用双指针来进行操作了。

一开始是想，如果指针指到了d[i]字符串的最后一个元素，就可以判定这个字符串满足要求。可是，如果指到最后一个元素，s中却找不到元素和d[i]字符串最后一个元素相等，是不满足题目要求的。因此，我在代码当中加入了一个Flag布尔变量，来判断访问到最后一个元素，且相等的情况。

在把所有的最大长度的单词放进ArrayList里面之后，我们需要对ArrayList里面的元素进行排序。在这里，可以直接使用ArrayList里面的内建函数，sort(String::compareTo)来进行排序。也可以直接通过比较String长度的最值，维护一个最长的String，这样可以降低时间复杂度。代码中仍然演示了ArrayList的排序方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Solution {
    public String findLongestWord(String s, List<String> d) {
        ArrayList<String> candidate = new ArrayList<String>();
        int length = s.length();
        if (length == 0) return "";
        int max = 0;
        for (String cur : d) {
            int curlen = cur.length();
            int i = 0;
            int j = 0;
            boolean flag = false;
            while (j < length) {
                char a = cur.charAt(i);
                char b = s.charAt(j);
                if (cur.charAt(i) == s.charAt(j)) {
                    if (i < curlen - 1){
                        i++;
                        j++;
                    }
                    else if (i == curlen - 1){
                        flag = true;
                        j++;
                    }
                } else {
                    j++;
                }
            }
            if (flag) {
                if (curlen > max) {
                    candidate.clear();
                    candidate.add(cur);
                    max = curlen;
                } else if (curlen == max) {
                    candidate.add(cur);
                }
            }
        }
        if (candidate.isEmpty()) return "";
        else {
            candidate.sort(String::compareTo);
            return candidate.get(0);
        }
    }
}