# 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```里面所有出现过的字符的位置

如果刚好读到```s```的最后一位 ```idx```会等于```n``` 而不是-1
对于```word```中的每个单词 我们先初始令```idx=0 ```然后一直```idx=next[idx][ch]``` 直到```idx=-1```为止 如果某个```idx=-1``` 并且还没有到达```word```的末尾 就说明```word```不是```s```的subquence
## Code

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;
}
}