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.

class Solution {
    public String findLongestWord(String s, List<String> d) {
        Collections.sort(d, (a, b) -> (a.length() != b.length()) ? -Integer.compare(a.length(), b.length()) : a.compareTo(b));
        
        for(String st : d) {
            int i = 0;
            for(char c : s.toCharArray()) {
                if(c == st.charAt(i)) {
                    i++;
                }
                if(i == st.length()) return st;
            }
        }
        return "";
    }
}

 

不是trie 不是trie，好久没做题想太多了。先按照从长到短和lexico从小到大排序字典里的string

然后从头到尾遍历string,设置i为相同的位数，如果相同char就i++，到i和st长度一样的时候就return st