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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting

题目描述:

给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。

示例 1：

输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"

示例 2：

输入：s = "abpcplea", dictionary = ["a","b","c"]
输出："a"

题目分析:

子序列指的是从字符串中顺序取出字符，但是可以不连续。

1. 因此题目就是求，数组dictionary中s的最长子序列
2. 最长子序列如果存在多个，返回字典序最小的一个
3. 数组dictionary中不存在s的子序列，返回空字符串

思路:

• 初始化有序容器 set, i = 0 (0 <= i < dictionary.size())
• 循环dictionary
• 判断当前元素dictionary[i]是否是s子序列
• • 是，判断dictionary[i]长度是大于还是等于之前求出的子序列
• • • 大于，丢弃之前的子序列(清空set),添加dictionary[i]到容器 set.
• • • 等于，添加dictionary[i]到容器 set.
• • 否,开始下一个元素dictionary[i + 1],重复上面的操作

遍历完dictionary的所有元素之后，返回set的第一个元素即可(set为有序容器)。

代码实现:

class Solution {
    public TreeSet<String> set = new TreeSet<>(); // 有序容器.
    public String findLongestWord(String str, List<String> dictionary) {
        int max_len = 0;
        int str_len = str.length();
        int words_len = dictionary.size();
        for (int i = 0; i < words_len; i++) {
            String word = dictionary.get(i);
            int word_len = word.length();
            int idx = 0, j = 0;
            while (j < str_len && idx < word_len) { // 判断是否为子序列
               if (max_len != 0 && word_len < max_len) break; // 如果当前元素比已经找到的子序列小,则跳过.
                int x = word_len - idx;
                int y = str_len - j;
                if (x > y) break;
                if (str.charAt(j) == word.charAt(idx)) idx++;
                j++;
            }
             if (idx == word_len) { // 是子序列
                if (idx > max_len) { // 大于之前找到的子序列
                    max_len = idx; // 更新最长子序列标记
                    set.clear(); // 清空容器
                    set.add(word); // 添加子序列
                } else if (idx == max_len) { // 等于之前的子序列
                    set.add(word);  // 添加到有序容器
                }
            }
        }
        if (set.isEmpty()) return "";
        return set.first();
    }
}

思路二:(从题解看来的)

因为要求的是最长且字典序最小的子序列，因此可以在对dictionary 进行遍历判断之前，先进行一次排序。
排序的规则则是按照字符串长度由大到小，字典序由小到大。这样的话，在遍历dictionary的过程中，找到的第一个子序列就是要求的最大且字典序最小的子序列，就可以直接返回了。

代码实现:

省略.jpg
可以自己尝试写一下，把思路一的代码做些修改即可。