Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public static class PrefixTreeNode {
- private final Character c;
- private final PrefixTreeNode[] children = new PrefixTreeNode[27];
- private final PrefixTreeNode parent;
- public PrefixTreeNode(Character c, PrefixTreeNode parent) {
- this.c = c;
- this.parent = parent;
- }
- public boolean hasChild(Character c) {
- return children[((int) c.charValue()) - 96] != null;
- }
- public PrefixTreeNode getChild(Character c) {
- return children[((int) c.charValue()) - 96];
- }
- public void addChild(Character c, PrefixTreeNode node) {
- children[((int) c.charValue()) - 96] = node;
- }
- public PrefixTreeNode getParent() {
- return parent;
- }
- }
- public List<String> findWords(char[][] board, String[] words) {
- HashSet<String> wordsDic = new HashSet<String>(Arrays.asList(words));
- if (words.length == 0 || board.length == 0 || board[0].length == 0) {
- return new LinkedList<String>();
- }
- if (board.length == 1 && board[0].length == 1 && wordsDic.contains("" + board[0][0])) {
- return new LinkedList<String>(Arrays.asList("" + board[0][0]));
- }
- PrefixTreeNode prefixTreeRoot = buildPrefixTree(words);
- LinkedList<String> result = traverseTheBoard(board, prefixTreeRoot, wordsDic);
- return result;
- }
- private LinkedList<String> traverseTheBoard(char[][] board, PrefixTreeNode prefixTreeRoot, HashSet<String> wordsDic) {
- HashSet<String> result = new HashSet<>();
- for (int x = 0; x < board.length; x++) {
- for (int y = 0; y < board[0].length; y++) {
- result.addAll(dfs(board, x, y, prefixTreeRoot, wordsDic, new HashSet<>()));
- }
- }
- return new LinkedList<>(result);
- }
- private Set<String> dfs(char[][] board, int x, int y, PrefixTreeNode node, HashSet<String> wordsDic, HashSet<Coordinates> pathSoFar) {
- HashSet<String> globalResult = new HashSet<>();
- // jump to next node in prefix tree and fail fast if no prefix exist for given path
- char c = board[x][y];
- node = node.getChild(c);
- if (node == null) {
- return globalResult;
- }
- // calculate available options excluding visited points
- ArrayList<Coordinates> nextPoints = getConnectedPoints(x, y, board, pathSoFar);
- pathSoFar.add(new Coordinates(x, y));
- // check if we found a word
- String word = buildWhatWeveGotSoFar(node);
- if (wordsDic.contains(word)) {
- globalResult.add(word);
- }
- // go deeper
- for (Coordinates nextPoint : nextPoints) {
- HashSet<Coordinates> pathSoFarCloned = new HashSet<>(pathSoFar);
- globalResult.addAll(dfs(board, nextPoint.x, nextPoint.y, node, wordsDic, pathSoFarCloned));
- }
- return globalResult;
- }
- private String buildWhatWeveGotSoFar(PrefixTreeNode node) {
- Stack<Character> stack = new Stack<>();
- PrefixTreeNode nextNode = node;
- while (nextNode.c != null) {
- stack.add(nextNode.c);
- nextNode = nextNode.getParent();
- }
- StringBuilder builder = new StringBuilder();
- while(!stack.isEmpty()) {
- builder.append(stack.pop());
- }
- return builder.toString();
- }
- private ArrayList<Coordinates> getConnectedPoints(int x, int y, char[][] board, HashSet<Coordinates> pathSoFar) {
- ArrayList<Coordinates> result = new ArrayList<>();
- int max_x = board.length - 1;
- int max_y = board[0].length - 1;
- if (x > 0) {
- Coordinates newCoor = new Coordinates(x - 1, y);
- if (!pathSoFar.contains(newCoor)) {
- result.add(newCoor);
- }
- }
- if (x < max_x) {
- Coordinates newCoor = new Coordinates(x + 1, y);
- if (!pathSoFar.contains(newCoor)) {
- result.add(newCoor);
- }
- }
- if (y > 0) {
- Coordinates newCoor = new Coordinates(x, y - 1);
- if (!pathSoFar.contains(newCoor)) {
- result.add(newCoor);
- }
- }
- if (y < max_y) {
- Coordinates newCoor = new Coordinates(x, y + 1);
- if (!pathSoFar.contains(newCoor)) {
- result.add(newCoor);
- }
- }
- return result;
- }
- public static class Coordinates {
- public int x;
- public int y;
- public Coordinates(int x, int y) {
- this.x = x;
- this.y = y;
- }
- @Override
- public boolean equals(Object o) {
- if (this == o) return true;
- if (o == null || getClass() != o.getClass()) return false;
- Coordinates that = (Coordinates) o;
- if (x != that.x) return false;
- return y == that.y;
- }
- @Override
- public int hashCode() {
- int result = x;
- result = 31 * result + y;
- return result;
- }
- }
- private PrefixTreeNode buildPrefixTree(String[] words) {
- PrefixTreeNode root = new PrefixTreeNode(null, null);
- for (String word : words) {
- PrefixTreeNode currentNode = root;
- for (Character c : word.toCharArray()) {
- if (currentNode.hasChild(c)) {
- currentNode = currentNode.getChild(c);
- } else {
- PrefixTreeNode newNode = new PrefixTreeNode(c, currentNode);
- currentNode.addChild(c, newNode);
- currentNode = newNode;
- }
- }
- }
- return root;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement