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

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

class Solution {

    public String findLongestWord(String s, List<String> dictionary) {
        List<String> list = new LinkedList<>();

        for (String word : dictionary) {
            if (isContain(word, s)) {
                list.add(word);
            }
        }
        if(list.isEmpty()) {
            return "";
        }
        Collections.sort(list);
        int idx = list.size() - 1, len = list.get(idx).length();

        for (int i = list.size() - 1; i >= 0; i--) {
            if (list.get(i).length() >= len) {
                len = list.get(i).length();
                idx = i;
            }
        }
        return list.get(idx);
    }

    /**
     * 判断是否可以通过删除 word2 中的某些字符得到 word1
     */
    private boolean isContain(String word1, String word2) {
        int i = 0, j = 0;
        StringBuilder sb = new StringBuilder();
        for (; i < word1.length(); i++) {
            char ch = word1.charAt(i);
            while (j < word2.length()) {
                if (word2.charAt(j) == ch) {
                    sb.append(word2.charAt(j));
                    j++;
                    break;
                }
                j++;
            }
        }
        return sb.toString().equals(word1);
    }