524. Longest Word in Dictionary through Deleting

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.

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.

-------------------
这题就是暴力解. 注意：计算isSubset⼀个循环就够了，复杂度是线性的
Solution #1 O(d * n * log n + n * m), m是s的⻓度，n是dic的⼤小，d是dic⾥面string的平均长度

class Solution {
    public String findLongestWord(String s, List<String> d) {
        Collections.sort(d, (a, b) -> {
            if (a.length() == b.length()) {
                return a.compareTo(b);
            }
            return b.length() - a.length();
        });
        
        for (String sub : d) {
            if (isSubset(s, sub)) return sub;
        }
        
        return "";
    }
    
    private boolean isSubset(String s, String t) {
        int j = 0;
        for (int i = 0; i < s.length() && j < t.length(); i++) {
           if (s.charAt(i) == t.charAt(j)) {
                j++;
            }
        }
        
        return j == t.length();
    }
}

Solution #2 不sort，直接比较反⽽更快 O(n * m), n是dic的⼤小，m是s的⻓度

class Solution {
    public String findLongestWord(String s, List d) {
        String rt = "";
        for (String sub : d) {
            if (isSubset(s, sub) 
                && (rt.length() < sub.length() 
                    || (rt.length() == sub.length() && rt.compareTo(sub) > 0))) {
                
                rt = sub;
            }
        }
        
        return rt;
    }
    
    private boolean isSubset(String s, String t) {
        int j = 0;
        for (int i = 0; i < s.length() && j < t.length(); i++) {
           if (s.charAt(i) == t.charAt(j)) j++;
        }
        
        return j == t.length();
    }
}