Solution 1Trie Backtrack
class Trie:
def __init__(self):
self.children = {}
self.isWord = False
def add(self, word: str):
cur = self
for i, ch in enumerate(word):
if ch not in cur.children: cur.children[ch] = Trie()
cur = cur.children[ch]
cur.isWord = True
def remove(self, word: str):
cur = self
nodes = []
for i, ch in enumerate(word):
if ch not in cur.children: return
nodes.append(cur)
cur = cur.children[ch]
cur.isWord = False
i = -1
while nodes:
parent = nodes.pop()
if len(cur.children) > 0 or cur.isWord: return
parent.children.pop(word[i])
cur = parent
i -= 1
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
found = set()
trie = Trie()
for word in words: trie.add(word)
row, col = len(board), len(board[0])
visited = set()
def search(r, c, parent, visited, word):
if (r < 0 or c < 0 or r >= row or c >= col or (r,c) in visited or board[r][c] not in parent.children): return
word += board[r][c]
parent = parent.children[board[r][c]]
if parent.isWord:
found.add(word)
trie.remove(word)
visited.add((r,c))
search(r+1, c, parent, visited, word)
search(r, c+1, parent, visited, word)
search(r-1, c, parent, visited, word)
search(r, c-1, parent, visited, word)
visited.remove((r, c))
for r in range(row):
for c in range(col):
search(r, c, trie, visited, "")
return list(found)class Trie {
public Trie[] children;
public int numberOfChildren;
public String wordValue;
public Trie() {
children = new Trie[26];
numberOfChildren = 0;
wordValue = null;
}
public void add(String word) {
Trie node = this;
for (char ch: word.toCharArray()) {
int i = ch - 'a';
if (node.children[i] == null) {
node.children[i] = new Trie();
node.numberOfChildren++;
}
node = node.children[i];
}
node.wordValue = word;
}
public void remove(String word) {
Trie parentOfChild = null;
int childIndexforDelete = 0;
Trie node = this;
for (char ch: word.toCharArray()) {
int i = ch - 'a';
if (node.children[i] == null) {
return ;
}
if (node.numberOfChildren > 1 || (node.wordValue != null && node.numberOfChildren == 1)) {
parentOfChild = node;
childIndexforDelete = i;
}
node = node.children[i];
}
node.wordValue = null;
if (node.numberOfChildren == 0 && parentOfChild != null) {
parentOfChild.children[childIndexforDelete] = null;
parentOfChild.numberOfChildren--;
}
}
}
class Solution {
private int rowMax;
private int colMax;
private int boardMax;
private char[][] board;
private Trie root;
private boolean[][] visited;
private List<String> output;
public List<String> findWords(char[][] board, String[] words) {
output = new ArrayList<String>();
rowMax = board.length;
colMax = board[0].length;
boardMax = rowMax * colMax;
this.board = board;
root = new Trie();
visited = new boolean[rowMax][colMax];
// Prune obvious false words
int[] boardCount = new int[26];
for (char[] row: board) {
for (char ch: row) {
boardCount[ch - 'a']++;
}
}
for (String word: words) {
if (word.length() > boardMax) {
continue;
}
int[] wordCount = new int[26];
for (char ch: word.toCharArray()) {
int i = ch - 'a';
wordCount[i]++;
if (wordCount[i] > boardCount[i]) {
continue;
}
}
root.add(word);
}
// dfs
for (int r = 0; r < rowMax; r++) {
for (int c = 0; c < colMax; c++) {
dfs(root, r, c);
}
}
return output;
}
public void dfs(Trie node, int r, int c) {
if (r < 0 || r >= rowMax || c < 0 || c >= colMax || visited[r][c] || node.children[board[r][c] - 'a'] == null) {
return ;
}
node = node.children[board[r][c] - 'a'];
visited[r][c] = true;
if (node.wordValue != null) {
output.add(node.wordValue);
root.remove(node.wordValue);
}
dfs(node, r+1, c);
dfs(node, r-1, c);
dfs(node, r, c+1);
dfs(node, r, c-1);
visited[r][c] = false;
}
}Solution 2Pruned Trie
Same thing not much difference, just added same pruning, didn't make much difference, Over engineered!
Python
class PrefixTree:
'''
Same thing not much difference, just added same pruning, didn't make much difference, Over engineered!
'''
def __init__(self) -> None:
self.children = {}
self.isWord = None
def add(self, word: str) -> None:
root = self
for ch in word:
if ch not in root.children:
root.children[ch] = PrefixTree()
root = root.children[ch]
root.isWord = word
def remove(self, word: str) -> str:
if not word: # Not needed
return None
root = self
deleteLink = (root, word[0])
for ch in word:
if len(root.children) > 1 or root.isWord:
deleteLink = (root, ch)
if ch not in root.children:
return None
root = root.children[ch]
if not root.children:
deleteLink[0].children.pop(deleteLink[1])
root.isWord = None
return word
def __str__(self) -> str:
return f'Node:(children={self.children.keys()}, isWord={self.isWord})'
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
# Prune words
words = set(words)
boardCounter = sum((Counter(row) for row in board),Counter())
self.allWords = dict()
while words:
word = words.pop()
if len(word) > len(board)*len(board[0]):
continue
wordCounter = Counter(word)
for ch in wordCounter:
if wordCounter[ch] > boardCounter[ch]:
continue
# Optimize branching (doesn't contribute much), ideal would be to see if there's any algo for word commanlity, reduce number of prefix branches..
reverseWord = word[::-1]
key = word
if boardCounter[word[0]] > boardCounter[word[-1]]:
key = reverseWord
# Reduce Prefix tree branches by reducing number of words to search
if reverseWord in words:
words.remove(reverseWord)
self.allWords[key] = [word, reverseWord]
else:
self.allWords[key] = [word]
self.visited = set()
for r in range(len(board)):
self.visited.update([(r,-1), (r,len(board[0]))])
for c in range(len(board[0])):
self.visited.update([(-1,c), (len(board),c)])
self.prefixTree = PrefixTree()
for word in self.allWords:
self.prefixTree.add(word)
self.board = board
self.output = []
for r in range(len(board)):
for c in range(len(board[0])):
self.search(r,c,self.prefixTree)
return self.output
def search(self, r: int, c: int, node: PrefixTree) -> None:
if not node: # Not needed
return
if node.isWord:
self.output.extend(self.allWords.pop(node.isWord, []))
self.prefixTree.remove(node.isWord)
if (r,c) in self.visited or self.board[r][c] not in node.children:
return
node = node.children[self.board[r][c]]
self.visited.add((r,c))
self.search(r-1, c, node)
self.search(r+1, c, node)
self.search(r, c-1, node)
self.search(r, c+1, node)
self.visited.remove((r,c))
return