Created
March 29, 2022 02:26
-
-
Save ali-alaei/123a840cf638178a67e310b238997d9b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.*; | |
class TrieNode { | |
//Hash map of character to trie node | |
HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>(); | |
//A string to store the possible found words for each node | |
String word = null; | |
public TrieNode() {} | |
} | |
class Solution { | |
char[][] _board = null; | |
//The list of found words | |
ArrayList<String> _result = new ArrayList<String>(); | |
public List<String> findWords(char[][] board, String[] words) { | |
//Step 1). Construct the Trie | |
TrieNode root = new TrieNode(); | |
//Looping over each word in words list | |
for (String word : words) { | |
//Node is the index on Trie nodes. Which initially points to the root | |
TrieNode node = root; | |
//looping over each letter of the word | |
for (Character letter : word.toCharArray()) { | |
//Checking if the current node's children contain the current | |
//letter being looped over | |
if (node.children.containsKey(letter)) { | |
//Moving the index to the node that contains the letter | |
node = node.children.get(letter); | |
} | |
//Else, create a new child node for the current node containing | |
//the letter | |
else { | |
TrieNode newNode = new TrieNode(); | |
node.children.put(letter, newNode); | |
//Updating the index to the new node | |
node = newNode; | |
} | |
} | |
node.word = word; //Storing words in Trie (Optimization) | |
} | |
this._board = board; | |
//Step 2). Backtracking starting for each cell on the board | |
for (int row = 0; row < board.length; ++row) { | |
for (int col = 0; col < board[row].length; ++col) { | |
if (root.children.containsKey(board[row][col])) { | |
backtracking(row, col, root); | |
} | |
} | |
} | |
return this._result; | |
} | |
private void backtracking(int row, int col, TrieNode parent) { | |
//Current character on the board | |
Character letter = this._board[row][col]; | |
//The node containing the current letter | |
TrieNode currNode = parent.children.get(letter); | |
//Checking if the node contains a word | |
if (currNode.word != null) { | |
//Adding the word to the results and removing it from the node | |
//to prevent duplication in the results | |
this._result.add(currNode.word); | |
currNode.word = null; | |
} | |
//Marking the current letter before the EXPLORATION | |
this._board[row][col] = '#'; | |
//Exploring neighbor cells in around-clock directions: up, right, | |
//down, left | |
int[] rowOffset = {-1, 0, 1, 0}; | |
int[] colOffset = {0, 1, 0, -1}; | |
for (int i = 0; i < 4; ++i) { | |
int newRow = row + rowOffset[i]; | |
int newCol = col + colOffset[i]; | |
//If Column or Row is out of the boundary, skip | |
if (newRow < 0 || newRow >= this._board.length || newCol < 0 | |
|| newCol >= this._board[0].length) { | |
continue; | |
} | |
if (currNode.children.containsKey(this._board[newRow][newCol])) { | |
backtracking(newRow, newCol, currNode); | |
} | |
} | |
//End of EXPLORATION, restore the original letter on the board. | |
this._board[row][col] = letter; | |
//Optimization: incrementally remove the leaf nodes | |
if (currNode.children.isEmpty()) { | |
parent.children.remove(letter); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment