# 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

```java
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.
*/
```