Subsequence

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.

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

Output: "apple"

看见这题之后，要想到答案更有出现在比较长的word里，所以需要一个容器来自动帮我们排序长度，并且保存该长度下的所有string。所以我们想到使用TreeMap。

首先将对应的string都放到map里，然后根据长度从大到小遍历对应的list，如果我们的s的subsequence是其中的某个单词，那么就可以直接返回。

但是要注意的是，因为某个长度的list里面，可能会存在多个满足条件的单词，根据题意我们需要根据字典序最小输出，所以我们用一个叫candidates的list保存，sort之后输出。

class Solution {
    public String findLongestWord(String s, List<String> d) {

        TreeMap<Integer, List<String>> map = new TreeMap<>((o1, o2) -> (o2-o1));

        for(String str : d) {
            int len = str.length();
            map.putIfAbsent(len, new ArrayList<>());
            map.get(len).add(str);
        }

        List<String> candidates = new ArrayList<>();

        for(Integer len : map.keySet()) {
            List<String> words = map.get(len);

            for(String word : words) {
                if(isSubsequence(s, word)) {
                    candidates.add(word);
                }
            }

            if(candidates.size() > 0) {
                break;
            }
        }

        if(candidates.size() == 0) {
            return "";
        }

        Collections.sort(candidates);
        return candidates.get(0);
    }

    // 知道如何确定a是b的subsequence很重要!
    public boolean isSubsequence(String a, String b) {
        int i = 0, j = 0;
        while(i < a.length() && j < b.length()) {
            if(a.charAt(i) == b.charAt(j)) {
                j++;
            }
            i++;
        }
        return j == b.length();
    }
}

xiedaxia1hao / leetcode_pattern

String #9

Subsequence vs. Substring

Subsequence

524. Longest Word in Dictionary through Deleting