Implement Trie (Prefix Tree)
A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
class Node {
Character value;
Node[] children;
boolean end;
public Node(Character value) {
this.value = value;
this.children = new Node[26];
this.end = false;
}
public Node getChild(char ch) {
return children[ch - 'a'];
}
public Node addChild(Node child) {
this.children[child.value - 'a'] = child;
return child;
}
}
class Trie {
Node root;
public Trie() {
root = new Node(null);
}
public void insert(String word) {
boolean end;
if (word.length() > 0) {
Node node = root;
int i = 0;
do {
Character ch = Character.valueOf(word.charAt(i));
end = i == word.length()-1;
Node child = node.getChild(ch);
if (child == null) {
child = node.addChild(new Node(ch));
}
child.end = end || child.end;
node = child;
i++;
} while (!end);
}
}
public boolean search(String word) {
return search(word, false);
}
public boolean startsWith(String prefix) {
return search(prefix, true);
}
private boolean search(String word, boolean prefix) {
int i = 0;
Node node = root;
while (true) {
Character ch = Character.valueOf(word.charAt(i));
Node child = node.getChild(ch);
if (child == null) {
return false;
}
if (i == word.length() - 1) {
return prefix ? true : child.end;
}
i++;
node = child;
}
}
}
#36. Design Add and Search Words Data Structure
Design a data structure that supports adding new words and finding if a string matches any previously added string. The searched word may contain dots '.' where dots can be matched with any letter.
class Node {
Character value;
Node[] children;
boolean end;
public Node(Character value) {
this.value = value;
this.children = new Node[26];
this.end = false;
}
public Node getChild(char ch) {
return children[ch - 'a'];
}
public Node addChild(Node child) {
this.children[child.value - 'a'] = child;
return child;
}
}
class WordDictionary {
Node root;
public WordDictionary() {
root = new Node(null);
}
public void addWord(String word) { // la fel ca la Trie
boolean end;
if (word.length() > 0) {
Node node = root;
int i = 0;
do {
Character ch = Character.valueOf(word.charAt(i));
end = i == word.length()-1;
Node child = node.getChild(ch);
if (child == null) {
child = node.addChild(new Node(ch));
}
child.end = end || child.end;
node = child;
i++;
} while (!end);
}
}
public boolean search(String word) {
return search(word, root, 0);
}
private boolean search(String word, Node node, int i) {
while (i < word.length()) {
Character ch = Character.valueOf(word.charAt(i));
boolean isLetter = ch != '.';
if (isLetter) {
Node child = node.getChild(ch);
if (child == null) {
return false;
}
if (i == word.length() - 1) {
return child.end;
}
node = child;
i++;
} else { // in plus fata de Trie, match pe caracterul '.'
for (int j=0; j<node.children.length; j++) {
Node child = node.children[j];
if (child != null) { // match condition
if (i == word.length() - 1 && child.end) {
return true;
}
boolean res = search(word, child, i+1);
if (res) {
return true;
}
}
}
return false;
}
}
return false;
}
}
Given an m x n board of characters and a list of strings words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
class Node {
Character value;
Node[] children;
boolean end;
int kidsCount; // camp aditional
Node parent; // camp aditional
public Node(Character value) {
this.value = value;
this.children = new Node[26];
this.end = false;
this.kidsCount = 0;
this.parent = null;
}
public Node getChild(char ch) {
return children[ch - 'a'];
}
public Node addChild(Node child) {
child.parent = this;
this.children[child.value - 'a'] = child;
this.kidsCount++;
return child;
}
public void removeChild(char ch) {
children[ch - 'a'] = null;
this.kidsCount--;
}
public boolean hasChild() {
return this.kidsCount > 0;
}
}
enum SearchStatus {
NOT_FOUND,
PREFIX,
FOUND
};
class Trie {
Node root;
public Trie() {
root = new Node(null);
}
public void insert(String word) { // identic Trie
boolean end;
if (word.length() > 0) {
Node node = root;
int i = 0;
do {
Character ch = Character.valueOf(word.charAt(i));
end = i == word.length()-1;
Node child = node.getChild(ch);
if (child == null) {
child = node.addChild(new Node(ch));
}
child.end = end || child.end;
node = child;
i++;
} while (!end);
}
}
public void remove(String word) { // metoda noua
int i = 0;
Node node = root;
while (i < word.length()) {
Character ch = Character.valueOf(word.charAt(i));
Node child = node.getChild(ch);
i++;
node = child;
}
while (node != root) {
if (node.hasChild()) {
node.end = false;
break;
}
node.parent.removeChild(node.value);
node = node.parent;
}
}
public SearchStatus search(String word) {
int i = 0;
Node node = root;
while (true) {
Character ch = Character.valueOf(word.charAt(i));
Node child = node.getChild(ch);
if (child == null) {
return SearchStatus.NOT_FOUND;
}
if (i == word.length() - 1) {
return child.end ? SearchStatus.FOUND : SearchStatus.PREFIX;
}
i++;
node = child;
}
}
}
class Solution {
public List<String> findWords(char[][] board, String[] words) {
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
List<String> result = new ArrayList<>();
for (int i=0; i<board.length; i++) {
for (int j=0; j<board[i].length; j++) {
check(i, j, board, "", trie, "", result);
}
}
return result;
}
private void hunt(int i, int j, char[][] board, String word, Trie trie, String path, List<String> result) {
// left
check(i, j-1, board, word, trie, path, result);
// right
check(i, j+1, board, word, trie, path, result);
// up
check(i-1, j, board, word, trie, path, result);
// down
check(i+1, j, board, word, trie, path, result);
}
private void check(int i, int j, char[][] board, String word, Trie trie, String path, List<String> result) {
if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) {
return;
}
if (!isNewPos(i, j, path)) {
return;
}
word = word + board[i][j];
SearchStatus status = trie.search(word);
switch (status) {
case SearchStatus.FOUND:
result.add(word);
trie.remove(word); // optimizare: stergere cuvant dupa ce a fost adaugat la rezultat
case SearchStatus.PREFIX:
path = path + getPosKey(i,j);
hunt(i, j, board, word, trie, path, result);
}
}
private String getPosKey(int i, int j) {
return i + "-" + j + "#";
}
private boolean isNewPos(int i, int j, String path) {
int index = path.indexOf(getPosKey(i, j));
if (index < 0) {
return true;
}
if (index == 0) {
return false;
}
char ch = path.charAt(index - 1);
return ch != '#';
}
}
