524. Longest Word in Dictionary through Deleting

Problem

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: All the strings in the input will only contain lower-case letters. The size of the dictionary won’t exceed 1,000. The length of all the strings in the input won’t exceed 1,000.

Ideas

First sort the dict then use two pointer to compare input string and word in the dict, if the word by be formated by deleting some number of chars in the input string, return the current word as result.

Solution

public String findLongestWord(String s, List<String> d) {
    // Sort strings in dict. Longer string and smaller lexicographical come first.
    Collections.sort(d, (a, b) -> {
       if (a.length() != b.length()) return b.length() - a.length();
       return a.compareTo(b);
    });
    
    for (String word : d) {
        if (isSubstr(s, word)) {
            return word;
        }
    }
    
    return "";
}

private boolean isSubstr(String s, String word) {
    int p1 = 0;
    int p2 = 0;
    char[] chs1 = s.toCharArray();
    char[] chs2 = word.toCharArray();
    // Check if chs2 is a part of chs1.
    while (p2 < chs2.length && p1 < chs1.length) {
        if (chs2[p2] == chs1[p1]) {
            p1++;
            p2++;
        } else {
            p1++;
        }
    }
    return p2 == chs2.length;
}