Amazon Interview Question
SDE-2sCountry: United States
/*
use a Trie structure where each node has a character and has a list of nodes.
*/
// iterative
class WordDictionary {
class Node {
Node[] letters;
boolean endOfWord;
public Node() {
letters = new Node[26];
endOfWord = false;
}
}
Node head;
/** Initialize your data structure here. */
public WordDictionary() {
head = new Node();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
if (word == null) {
return;
}
Node temp = head;
for (int i = 0; i < word.length(); ++i) {
if (temp.letters[word.charAt(i) - 'a'] == null) {
temp.letters[word.charAt(i) - 'a'] = new Node();
}
temp = temp.letters[word.charAt(i) - 'a'];
if (i == word.length() - 1) {
temp.endOfWord = true;
}
}
return;
}
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
public boolean search(String word) {
if (word == null) {
return false;
}
// bfs - iterative
Queue<Node> q = new LinkedList<>();
q.add(head);
for (int i = 0; i < word.length(); ++i) {
int size = q.size();
if (size == 0) {
return false;
}
if (word.charAt(i) == '.') {
while (size > 0) {
Node temp = q.remove();
Node[] tempLetters = temp.letters;
for (Node letter : tempLetters) {
if (letter != null) {
q.add(letter);
}
}
--size;
}
}
else {
while (size > 0) {
Node temp = q.remove();
Node[] tempLetters = temp.letters;
if (tempLetters[word.charAt(i) - 'a'] != null) {
q.add(tempLetters[word.charAt(i) - 'a']);
}
--size;
}
}
}
while (!q.isEmpty()) {
Node temp = q.remove();
if (temp.endOfWord) {
return true;
}
}
return false;
}
}
// recursive
class WordDictionary {
class Node {
Node[] letters;
boolean endOfWord;
public Node() {
letters = new Node[26];
endOfWord = false;
}
}
Node head;
/** Initialize your data structure here. */
public WordDictionary() {
head = new Node();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
if (word == null) {
return;
}
addWordUtil(word, 0, word.length() - 1, head);
return;
}
public void addWordUtil(String word, int currIdx, int endIdx, Node n) {
if (currIdx < endIdx) {
if (n.letters[word.charAt(currIdx) - 'a'] == null) {
n.letters[word.charAt(currIdx) - 'a'] = new Node();
}
addWordUtil(word, currIdx + 1, endIdx, n.letters[word.charAt(currIdx) - 'a']);
}
else if (currIdx == endIdx) {
if (n.letters[word.charAt(currIdx) - 'a'] == null) {
n.letters[word.charAt(currIdx) - 'a'] = new Node();
}
n.letters[word.charAt(currIdx) - 'a'].endOfWord = true;
}
return;
}
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
public boolean search(String word) {
if (word == null) {
return false;
}
// dfs - recursive
return searchUtil(word, 0, word.length() - 1, head);
}
public boolean searchUtil(String word, int currIdx, int endIdx, Node currNode) {
if (currIdx < endIdx) {
if (word.charAt(currIdx) == '.') {
for (Node letter : currNode.letters) {
if (letter != null && searchUtil(word, currIdx + 1, endIdx, letter)) {
return true;
}
}
}
else {
if (currNode.letters[word.charAt(currIdx) - 'a'] == null) {
return false;
}
else {
return searchUtil(word, currIdx + 1, endIdx, currNode.letters[word.charAt(currIdx) - 'a']);
}
}
}
else if (currIdx == endIdx) {
if (word.charAt(currIdx) == '.') {
for (Node letter : currNode.letters) {
if (letter != null && letter.endOfWord) {
return true;
}
}
}
else {
if (currNode.letters[word.charAt(currIdx) - 'a'] != null && currNode.letters[word.charAt(currIdx) - 'a'].endOfWord) {
return true;
}
}
}
return false;
}
}
We can create a Ternary search tree Or a Trie structure for dictionary word.
- rvedpathak4u July 31, 2020And can find out the words starting with part before *.
Later filter these words with the end part of the pattern.