0524. Longest Word in Dictionary through Deleting

https://leetcode.com/problems/longest-word-in-dictionary-through-deleting

Description

Given a string s and a string array dictionary, return the longest string in the dictionary that can be formed by deleting some of the given string characters. If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:

**Input:** s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
**Output:** "apple"

Example 2:

**Input:** s = "abpcplea", dictionary = ["a","b","c"]
**Output:** "a"

Constraints:

• 1 <= s.length <= 1000

• 1 <= dictionary.length <= 1000

• 1 <= dictionary[i].length <= 1000

• s and dictionary[i] consist of lowercase English letters.

ac

class Solution {
    public String findLongestWord(String s, List<String> d) {
        // edge cases
        if (s.length() == 0 || d.size() == 0) return "";

        // build search table
        List<Integer>[] map = new List[26];
        for (int i = 0; i < s.length(); i++) {
            int pos = s.charAt(i) - 'a';
            if (map[pos] == null) map[pos] = new ArrayList<>();
            map[pos].add(i);
        }

        // search word in d
        String res = "";
        for (String w : d) {
            if (!valid(map, w)) continue;
            if (w.length() > res.length() 
                || w.length() == res.length() && w.compareTo(res) < 0) 
                res = w;
        }

        return res;
    }

    private boolean valid(List<Integer>[] map, String w) {
        int prevCharIdx = 0;
        for (char c : w.toCharArray()) {
            int pos = c - 'a';
            if (map[pos] == null) return false; // this char not even in s
            int idx = Collections.binarySearch(map[pos], prevCharIdx);
            if (idx < 0) idx = - idx - 1; // < 0 means cant find, return (-insertion point -1)
            if (idx >= map[pos].size()) return false; // cant find this char
            prevCharIdx = map[pos].get(idx) + 1;
        }
        return true;
    }
}

/*
build a search table on s, each time search d is faster.
*/