LongestWordInDictionary [source code]
public class LongestWordInDictionary {
static
/******************************************************************************/
class Solution {
public String longestWord(String[] words) {
TrieNode root = new TrieNode ();
root.word = "-";
for (String word : words)
root.insert (word);
return dfs (root, "");
}
String dfs (TrieNode node, String accum) {
if (node == null || node.word.length () == 0)
return accum;
String res = "";
if (!node.word.equals ("-"))
accum = node.word;
for (TrieNode child : node.links) {
String curRes = dfs (child, accum);
if (curRes.length () > res.length () || (curRes.length () == res.length () && curRes.compareTo (res) < 0))
res = curRes;
}
return res;
}
/* Hand write this class every time you need to so you can remember well */
static class TrieNode {
String word = "";
TrieNode[] links = new TrieNode[26];
void insert (String s) {
char[] chs = s.toCharArray ();
TrieNode curNode = this;
for (int i = 0; i < chs.length; i++) {
int index = chs[i] - 'a';
if (curNode.links[index] == null)
curNode.links[index] = new TrieNode ();
curNode = curNode.links[index];
}
curNode.word = s;
}
/* Testing utility to peek into a node's links list */
String display () {
StringBuilder sb = new StringBuilder ();
sb.append ("word: " + this.word + '\n');
for (int i = 0; i < 26; i++) {
if (this.links[i] != null)
sb.append (String.format ("child %c -> %s\n", 'a' + i, this.links[i].word));
}
return sb.toString ();
}
}
}
/******************************************************************************/
public static void main(String[] args) {
LongestWordInDictionary.Solution tester = new LongestWordInDictionary.Solution();
String[][] inputs = {
{"w","wo","wor","worl","world"}, {"world"},
{"a", "banana", "app", "appl", "ap", "apply", "apple"}, {"apple"},
};
for (int i = 0; i < inputs.length / 2; i++) {
String[] words = inputs[2 * i];
String ans = inputs[2 * i + 1][0];
System.out.println (Printer.separator ());
String output = tester.longestWord (words);
System.out.printf ("%s -> %s, expected: %s\n",
Printer.array (words), Printer.wrapColor ('[' + output + ']', output.equals (ans) ? "green" : "red"), ans
);
}
}
}
题目意思还是挺清晰的, 不过就是想起来要建trie, 实在是有点头疼, 忘记的都差不多了;
关于trie问题, 以前一直没有特别强调的一个问题是, 跟link的index对应的这些letter, 在trie里面到底怎么对应关系? 现在上了NLP大概知道这个对应关系, 就是letter对应的, 其实就是edge, 而不是某一个node;
这题的hint给的比较大度, 直接按照hint的思路来写, 好像其实也是没有什么难度的, 不过trie这个问题反正是没有办法解决的, 所以我觉得还是利用这一题的机会来复习一下trie算了;
trie建立部分倒是很快写出来了, 然后准备用BFS来写traverse:
Queue<TrieNode> queue = new LinkedList<> ();
queue.offer (root);
String res = "";
while (!queue.isEmpty ()) {
int size = queue.size ();
for (int i = 0; i < size; i++) {
TrieNode cur = queue.poll ();
if (cur.word.length () > res.length () || (cur.word.length () == res.length () && cur.word.compareTo (res) < 0))
res = cur.word;
for (TrieNode child : cur.links) {
if (child != null)
queue.offer (child);
}
}
}
但是后来想了一下这里BFS好像不好, 因为我们这里并不是单纯的只关心depth; 所以我认为还是用DFS来写更好: 满足题意的leaf node应该是整个path上面都有word的那一个;
大概改了一下之后, 很愉快的就AC了, 提交了几次之后, 在波动范围内做到了16ms (99%)的submission最优解;
editorial1:
class Solution {
public String longestWord(String[] words) {
String ans = "";
Set<String> wordset = new HashSet();
for (String word: words) wordset.add(word);
for (String word: words) {
if (word.length() > ans.length() ||
word.length() == ans.length() && word.compareTo(ans) < 0) {
boolean good = true;
for (int k = 1; k < word.length(); ++k) {
if (!wordset.contains(word.substring(0, k))) {
good = false;
break;
}
}
if (good) ans = word;
}
}
return ans;
}
}
笨办法一个;
他还提供了另外一种写法:
class Solution {
public String longestWord(String[] words) {
Set<String> wordset = new HashSet();
for (String word: words) wordset.add(word);
Arrays.sort(words, (a, b) -> a.length() == b.length()
? a.compareTo(b) : b.length() - a.length());
for (String word: words) {
boolean good = true;
for (int k = 1; k < word.length(); ++k) {
if (!wordset.contains(word.substring(0, k))) {
good = false;
break;
}
}
if (good) return word;
}
return "";
}
}
总体思路还是类似的;
editorial2: 用trie和DFS;
Intuition: As prefixes of strings are involved, this is usually a natural fit for a trie (a prefix tree.) by @awicen
class Solution {
public String longestWord(String[] words) {
Trie trie = new Trie();
int index = 0;
for (String word: words) {
trie.insert(word, ++index); //indexed by 1
}
trie.words = words;
return trie.dfs();
}
}
class Node {
char c;
HashMap<Character, Node> children = new HashMap();
int end;
public Node(char c){
this.c = c;
}
}
class Trie {
Node root;
String[] words;
public Trie() {
root = new Node('0');
}
public void insert(String word, int index) {
Node cur = root;
for (char c: word.toCharArray()) {
cur.children.putIfAbsent(c, new Node(c));
cur = cur.children.get(c);
}
cur.end = index;
}
public String dfs() {
String ans = "";
Stack<Node> stack = new Stack();
stack.push(root);
while (!stack.empty()) {
Node node = stack.pop();
if (node.end > 0 || node == root) {
if (node != root) {
String word = words[node.end - 1];
if (word.length() > ans.length() ||
word.length() == ans.length() && word.compareTo(ans) < 0) {
ans = word;
}
}
for (Node nei: node.children.values()) {
stack.push(nei);
}
}
}
return ans;
}
}
他的这个代码我感觉写的不如我的, 不过这个人是一个大神, 我也不好多说什么了;
Letter = Edge
他每一个node里面存放的是char, 这个习惯我不喜欢, 我还是喜欢char对应edge的这个做法, 更加合理一些;
他的整体思路还是比较直接的, char直接对应node, 然后如果当前node可以end一个string, 那么就在node里面记录这个string的index, 后面DFS的时候直接用这个index取出来这个string就行了;
另外这个大神的DFS是用一个很类似BFS的方法写的; 自己在笔算画了一下 (不要用26叉的trie, 直接用BST就行了: 简单升级), 其实是一个PreOrder, 而且是一个反向的, 也就是node-right-left这样的顺序; 注意看他这里怎么处理continuous的: 要求node.end > 0才行, 如果不满足这个条件, 那么这个node的children就不会被push到Stack里面, 这个也就对应于我recursion写法里面的premature exit;
这样看来, 这个题目用我最开始的BFS来做应该也是可以的, 只不过我当时没有看到这个判断中断的方法而已: conditional push.
总体来说这个写法还是学到了不少东西的,
discussion里面有人提出一个有趣的看法:
@immiao said in Java solution with Trie:
Probably you can sort the array first. Then we can construct Trie without considering those unreachable words. In this way, you don't need
dfsto find the answer. Just keep track of the longest word while constructing Trie.
和对应的代码:
@ramya8 said in Java solution with Trie:
@immiao That's a really good idea!
class Solution {
class TrieNode{
public char val;
public TrieNode[] hash;
public TrieNode(){
this.val='\u0000';
this.hash=new TrieNode[26];
}
public TrieNode(char c){
this.val=c;
this.hash=new TrieNode[26];
}
}
public String longestWord(String[] words) {
TrieNode root=new TrieNode();
Arrays.sort(words);
String res="";
for(String word:words){
TrieNode curr=root;
for(int i=0;i<word.length();i++){
if(curr.hash[word.charAt(i)-'a']==null && i<word.length()-1)
break;
if(curr.hash[word.charAt(i)-'a']==null){
TrieNode temp=new TrieNode(word.charAt(i));
curr.hash[word.charAt(i)-'a']=temp;
}
curr=curr.hash[word.charAt(i)-'a'];
if(i==word.length()-1)
res= res.length() < word.length()? word : res;
}
}
return res;
}
}
总体来说还是很有意思的一个想法. 虽然说array of string的sort的cost不太好说, 不过应该是比一个DFS要少一些的; 注意这里DFS的cost是跟letter的count挂钩而不是word的count挂钩的;
submission领跑的几个DFS解法基本都是用我的这种node结构(string + (array of links)).
Problem Description
Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.
If there is no answer, return the empty string.
Example 1:
Input:
words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation:
The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".
Example 2:
Input:
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation:
Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".
Note:
- All the strings in the input will only contain lowercase letters.
- The length of words will be in the range [1, 1000].
- The length of words[i] will be in the range [1, 30].
Difficulty:Easy
Total Accepted:7.6K
Total Submissions:18.2K
Contributor:zestypanda
Companies
pinterest
Related Topics
hash tabletrie
Similar Questions
Longest Word in Dictionary through DeletingImplement Magic Dictionary
Hint 1
For every word in the input list, we can check whether all prefixes of that word are in the input list by using a Set.