[LeetCode] 524. Longest Word in Dictionary through Deleting

本文主要是介绍[LeetCode] 524. Longest Word in Dictionary through Deleting，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

题目大意

对s删除某些元素，使得删除后的s 为 d中的某个元素。

思路

trie

首先将建立tire，然后是用dfs搜索，遍历s。
boolean dfs(TrieNode node,String s,StringBuilder curSb,int index) ：是否有d的子树中的节点可以匹配。若有的话，该节点虽然是 isLeaf 也不需要比较。
其中：index 为s的下标。
若当前s[index] 有相应的子树，可以进入继续递归。否则index ++；
最后检查当前结点是否为d中的元素。
其实不会过。

boolean dfs(TrieNode node,String s,StringBuilder curSb,int index) ：

class TrieNode{char val;TrieNode[] nextNode = new TrieNode[26];boolean isLeaf;public TrieNode(char val){this.val = val;}
}class Trie{TrieNode root;public Trie(){root = new TrieNode('0');}public void insert(String s){TrieNode curNode = root;for(char ch : s.toCharArray()){if(curNode.nextNode[ch - 'a'] ==null){curNode.nextNode[ch - 'a'] = new TrieNode(ch);}curNode = curNode.nextNode[ch - 'a'] ;}curNode.isLeaf = true;}
}class Solution {String res = "";public String findLongestWord(String s, List<String> d) {Trie trie = new Trie();for(String ed : d){if(ed.length()>s.length())continue;trie.insert(ed);}StringBuilder curSb = new StringBuilder();dfs(trie.root,s,curSb,0);return res.toString();}boolean dfs(TrieNode node,String s,StringBuilder curSb,int index){boolean isExtend = false;for(int i = index ; i < s.length();i++){if(node.nextNode[s.charAt(i) - 'a'] == null)continue;curSb.append(s.charAt(i));isExtend = isExtend || dfs(node.nextNode[s.charAt(i) - 'a'],s,curSb,i+1);curSb.deleteCharAt(curSb.length()-1);}if(!isExtend && node.isLeaf == true && curSb.length() >= res.length()){String tCurSb = curSb.toString();if(curSb.length() > res.length() || tCurSb.compareTo(res)<0)res = tCurSb ;return true;}return false;}
}

逐个匹配

遍历d，对于每个元素ed，若s可以和ed匹配将ed记录，然后比较大小，返回答案。

class Solution {public String findLongestWord(String s, List<String> d) {String res = "";for(String ed : d){int i = 0 ;for(char ch:s.toCharArray()){if(i<ed.length() && ch == ed.charAt(i))i++;}if(i == ed.length() && i >= res.length())if(i> res.length() || ed.compareTo(res)<0)res = ed;}return res;}
}