Created
February 6, 2017 19:43
-
-
Save ejcer/838b853fdfbf146e94c7c3d7d327289c 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
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