Skip to content

Instantly share code, notes, and snippets.

@emcenrue emcenrue/stuff.java
Created Feb 6, 2017

Embed
What would you like to do?
public class Solution {
public List<String> findWords(char[][] board, String[] words) {
//insert all words into trie
//for each cell, depth first search from that cell in all directions checking each growing string against the trie
//if eventually a word is found (all neighbors dont continue making a valid word in trie), then add that word to soln list
//if at any added character the string no longer is in trie, stop traversing, just return null
Trie trie = new Trie();
for(int i = 0; i < words.length; i++){
trie.insert(words[i]);
}
List<String> validWords = new List<String>();
for(int row = 0; row < boards.length; row++){
for(int col = 0; col < boards[0].length; col++){
StringBuilder sb = new StringBuilder();
String validWord = testCharacterOnBoard(board, row, col, trie, sb, validWords);
}
}
}
public static void testCharacter(char[][] board, int row, int col, Trie trie, StringBuilder sb, List<String> validWords){
if(row < 0 || col < 0 || row >= board.length || col >= board[0].length){
return null;
}
//test current character in trie
sb.append(board[row][col]);
String curStr = sb.toString();
if(trie.startsWith(curStr)){
if(trie.search(curStr)){ //TODO figure out how to not duplicate the search
//there is this prefix, and it is a word
validWords.add(curStr);
}
//there is this prefix, but it isn't a word
//search surrounding characters
testCharacter(board, row+1, col, trie, sb, validWords); //use static list of validWords, otherwise you pass around a lot of memory
testCharacter(board, row-1, col, trie, sb, validWords);
testCharacter(board, row, col+1, trie, sb, validWords);
testCharacter(board, row, col-1, trie, sb, validWords);
}
//no such prefix was found, we're at a nonexistent dead word
//remove current character from sb
if (sb.length() > 0) {
sb.setLength(sb.length() - 1);
}
}
}
public class Trie {
private class TrieNode{
char val;
HashMap<Character, TrieNode> children;
public TrieNode(char ch){
val = ch;
children = new HashMap<Character, TrieNode>();
}
public TrieNode addChild(char ch){
if(this.children.containsKey(ch)){
return this.children.get(ch);
}else{
TrieNode child = new TrieNode(ch);
this.children.put(ch, child);
return child;
}
}
}
TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode(' ');
}
/** Inserts a word into the trie. */
public void insert(String word) {
char[] chArr = word.toCharArray();
this.insert(chArr, this.root, 0);
}
public void insert(char[] chArr, TrieNode currNode, int currIndex){
if(currIndex >= chArr.length){
return;
}
TrieNode child = currNode.addChild(chArr[currIndex]);
currIndex++;
insert(chArr, child, currIndex);
}
/** Returns true if the word is in the trie. */
public boolean search(String word) {
char[] chArr = word.toCharArray();
return search(chArr, this.root, 0);
}
public boolean search(char[] chArr, TrieNode currNode, int currIndex){
if(currIndex >= chArr.length){
return true;
}
if(currNode.children.containsKey(chArr[currIndex])){
TrieNode child = currNode.children.get(chArr[currIndex]);
currIndex++;
return search(chArr, child, currIndex);
}else{
return false;
}
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
char[] chArr = prefix.toCharArray();
return search(chArr, this.root, 0);
}
// public boolean startsWith(char[] chArr, TrieNode child, int currIndex){
// if(currIndex)
// }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.