Friday, May 4, 2018

LeetCode 720 - Longest Word in Dictionary

https://leetcode.com/problems/longest-word-in-dictionary/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].

• X.
https://leetcode.com/problems/longest-word-in-dictionary/discuss/109113/Java-Solution-with-Trie-+-BFS
        public String findLongestWord() {
String result = null;
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TrieNode node = queue.poll();
for (int j = 25; j >= 0; j--) {
if (node.children[j] != null && node.children[j].isWord) {//
result = node.children[j].word;
queue.offer(node.children[j]);
}
}
}
}
return result;
}


https://leetcode.com/problems/longest-word-in-dictionary/discuss/112720/JAVA-16ms-(99)-@-20180108-Trie+DFS:-clean-easy-explained-and-illustrated
Build a trie in the normal way, then do a dfs to find the longest continuous downward path from the root. This is not a particularly hard question in the context of trie, the point of this solution is to present a generic way of trie building and inserting that can be easily adapted to similar questions.
• Time Complexity: $O(\sum w_i)$, where $w_i$ is the length of words[i]. This is the complexity to build the trie and to search it.
If we used a BFS instead of a DFS, and ordered the children in an array, we could drop the need to check whether the candidate word at each node is better than the answer, by forcing that the last node visited will be the best answer.
• Space Complexity: $O(\sum w_i)$, the space used by our trie.

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


public String longestWord(String[] words) {
Arrays.sort(words, (s1, s2) -> {
if (s1.length() == s2.length())
return s1.compareTo(s2);
return Integer.compare(s1.length(), s2.length());
});

Trie trie = new Trie();
String lw = "";
for (String word : words) {
if (trie.insert(word)) {
if (lw.length() < word.length()) {
lw = word;
}
}
// System.out.println(trie);
}
return lw;
}

private static class TrieNode {
public TrieNode[] children = new TrieNode[26];
private boolean isEnd;

@Override
public String toString() {
return "TrieNode [children=" + Arrays.toString(children) + ", isEnd=" + isEnd + "]";
}
}

private static class Trie {

private TrieNode root = new TrieNode();

public boolean insert(String word) {
TrieNode cur = root;

boolean isComposed = true;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
TrieNode child = cur.children[ch - 'a'];

if (child == null) {
if (i != word.length() - 1) {
isComposed = false;
}
child = new TrieNode();
cur.children[ch - 'a'] = child;
} else {
if (i != word.length() - 1 && !child.isEnd) {
isComposed = false;
}
}
cur = child;
}
cur.isEnd = true;
return isComposed;
}

@Override
public String toString() {
return "Trie [root=" + root + "]";
}
}

X.

• Time complexity : $O(\sum w_i^2)$, where $w_i$ is the length of words[i]. Checking whether all prefixes of words[i] are in the set is $O(\sum w_i^2)$.
• Space complexity : $O(\sum w_i^2)$ to create the substrings.
    public String longestWord(String[] words) {
Set<String> wordset = new HashSet();
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 "";
}
    public String longestWord(String[] words) {
String ans = "";
Set<String> wordset = new HashSet();
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;
}
https://leetcode.com/problems/longest-word-in-dictionary/discuss/109114/JavaC++-Clean-Code
    public String longestWord(String[] words) {
Arrays.sort(words);
Set<String> built = new HashSet<String>();
String res = "";
for (String w : words) {
if (w.length() == 1 || built.contains(w.substring(0, w.length() - 1))) {
res = w.length() > res.length() ? w : res;
}
}
return res;
}