---
# System prepended metadata

title: 0524. Longest Word in Dictionary through Deleting
tags: [Leetcode, Medium, State Machine, Greedy]

---

# 0524. Longest Word in Dictionary through Deleting
###### tags: `Leetcode` `Medium` `Greedy` `State Machine`
Link: https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/description/
## 思路
和[0792. Number of Matching Subsequences](https://hackmd.io/kJSKSTwjQ5mpwooWYJuZQQ)一样
先得到```next[i][ch]```表示```s```中位置```i-1```右边第一个出现```ch```的位置 这里的时间复杂度是```O(26N) ```
所以```next[0]```里面存着```s```里面所有出现过的字符的位置
```next[n]```全都是-1 因为后面不再有东西了
如果刚好读到```s```的最后一位 ```idx```会等于```n``` 而不是-1
对于```word```中的每个单词 我们先初始令```idx=0 ```然后一直```idx=next[idx][ch]``` 直到```idx=-1```为止 如果某个```idx=-1``` 并且还没有到达```word```的末尾 就说明```word```不是```s```的subquence
## Code
```java=
class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        int n = s.length();
        int[][] next = new int[n+1][26];
        Arrays.fill(next[n], -1);
        for(int i=n; i>0; i--){
            for(int j=0; j<26; j++){
                next[i-1][j] = next[i][j];
            }
            next[i-1][s.charAt(i-1)-'a'] = i;
        }
        String ans = "";
        for(String word:dictionary){
            int idx = 0;
            boolean flag = false;
            for(int i=0; i<word.length(); i++){
                idx = next[idx][word.charAt(i)-'a'];
                if(idx==-1){
                    flag = true;
                    break;
                }
            }
            if(!flag){
                if(ans.length()<word.length()||(word.length()==ans.length() && word.compareTo(ans)<0)){
                    ans = word;
                }
            }
        }
        return ans;
    }
}
```