Advertisement
Guest User

Untitled

a guest
Jul 17th, 2018
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.89 KB | None | 0 0
  1. class Solution {
  2.     public static class PrefixTreeNode {
  3.         private final Character c;
  4.         private final PrefixTreeNode[] children = new PrefixTreeNode[27];
  5.         private final PrefixTreeNode parent;
  6.  
  7.         public PrefixTreeNode(Character c, PrefixTreeNode parent) {
  8.             this.c = c;
  9.             this.parent = parent;
  10.         }
  11.  
  12.         public boolean hasChild(Character c) {
  13.             return children[((int) c.charValue()) - 96] != null;
  14.         }
  15.  
  16.         public PrefixTreeNode getChild(Character c) {
  17.             return children[((int) c.charValue()) - 96];
  18.         }
  19.  
  20.         public void addChild(Character c, PrefixTreeNode node) {
  21.             children[((int) c.charValue()) - 96] = node;
  22.         }
  23.  
  24.         public PrefixTreeNode getParent() {
  25.             return parent;
  26.         }
  27.     }
  28.  
  29.     public List<String> findWords(char[][] board, String[] words) {
  30.         HashSet<String> wordsDic = new HashSet<String>(Arrays.asList(words));
  31.         if (words.length == 0 || board.length == 0 || board[0].length == 0) {
  32.             return new LinkedList<String>();
  33.         }
  34.         if (board.length == 1 && board[0].length == 1 && wordsDic.contains("" + board[0][0])) {
  35.             return new LinkedList<String>(Arrays.asList("" + board[0][0]));
  36.         }
  37.  
  38.  
  39.         PrefixTreeNode prefixTreeRoot = buildPrefixTree(words);
  40.  
  41.         LinkedList<String> result = traverseTheBoard(board, prefixTreeRoot, wordsDic);
  42.  
  43.         return result;
  44.     }
  45.  
  46.     private LinkedList<String> traverseTheBoard(char[][] board, PrefixTreeNode prefixTreeRoot, HashSet<String> wordsDic) {
  47.         HashSet<String> result = new HashSet<>();
  48.         for (int x = 0; x < board.length; x++) {
  49.             for (int y = 0; y < board[0].length; y++) {
  50.                 result.addAll(dfs(board, x, y, prefixTreeRoot, wordsDic, new HashSet<>()));
  51.             }
  52.         }
  53.  
  54.         return new LinkedList<>(result);
  55.     }
  56.  
  57.     private Set<String> dfs(char[][] board, int x, int y, PrefixTreeNode node, HashSet<String> wordsDic, HashSet<Coordinates> pathSoFar) {
  58.         HashSet<String> globalResult = new HashSet<>();
  59.        
  60.         // jump to next node in prefix tree and fail fast if no prefix exist for given path
  61.         char c = board[x][y];
  62.         node = node.getChild(c);                
  63.         if (node == null) {
  64.             return globalResult;
  65.         }
  66.  
  67.         // calculate available options excluding visited points
  68.         ArrayList<Coordinates> nextPoints = getConnectedPoints(x, y, board, pathSoFar);
  69.         pathSoFar.add(new Coordinates(x, y));
  70.  
  71.         // check if we found a word
  72.         String word = buildWhatWeveGotSoFar(node);
  73.         if (wordsDic.contains(word)) {
  74.             globalResult.add(word);
  75.         }
  76.        
  77.         // go deeper
  78.         for (Coordinates nextPoint : nextPoints) {
  79.             HashSet<Coordinates> pathSoFarCloned = new HashSet<>(pathSoFar);
  80.             globalResult.addAll(dfs(board, nextPoint.x, nextPoint.y, node, wordsDic, pathSoFarCloned));
  81.         }        
  82.  
  83.         return globalResult;
  84.     }
  85.  
  86.     private String buildWhatWeveGotSoFar(PrefixTreeNode node) {
  87.         Stack<Character> stack = new Stack<>();
  88.         PrefixTreeNode nextNode = node;
  89.         while (nextNode.c != null) {
  90.             stack.add(nextNode.c);
  91.             nextNode = nextNode.getParent();
  92.         }
  93.         StringBuilder builder = new StringBuilder();
  94.         while(!stack.isEmpty()) {
  95.             builder.append(stack.pop());
  96.         }
  97.         return builder.toString();
  98.     }
  99.  
  100.     private ArrayList<Coordinates> getConnectedPoints(int x, int y, char[][] board, HashSet<Coordinates> pathSoFar) {
  101.         ArrayList<Coordinates> result = new ArrayList<>();
  102.         int max_x = board.length - 1;
  103.         int max_y = board[0].length - 1;
  104.  
  105.         if (x > 0) {
  106.             Coordinates newCoor = new Coordinates(x - 1, y);
  107.             if (!pathSoFar.contains(newCoor)) {
  108.                 result.add(newCoor);
  109.             }
  110.         }
  111.         if (x < max_x) {
  112.             Coordinates newCoor = new Coordinates(x + 1, y);
  113.             if (!pathSoFar.contains(newCoor)) {
  114.                 result.add(newCoor);
  115.             }
  116.         }
  117.         if (y > 0) {
  118.             Coordinates newCoor = new Coordinates(x, y - 1);
  119.             if (!pathSoFar.contains(newCoor)) {
  120.                 result.add(newCoor);
  121.             }
  122.         }
  123.         if (y < max_y) {
  124.             Coordinates newCoor = new Coordinates(x, y + 1);
  125.             if (!pathSoFar.contains(newCoor)) {
  126.                 result.add(newCoor);
  127.             }
  128.         }
  129.  
  130.         return result;
  131.     }
  132.  
  133.     public static class Coordinates {
  134.         public int x;
  135.         public int y;
  136.  
  137.         public Coordinates(int x, int y) {
  138.             this.x = x;
  139.             this.y = y;
  140.         }
  141.  
  142.         @Override
  143.         public boolean equals(Object o) {
  144.             if (this == o) return true;
  145.             if (o == null || getClass() != o.getClass()) return false;
  146.  
  147.             Coordinates that = (Coordinates) o;
  148.  
  149.             if (x != that.x) return false;
  150.             return y == that.y;
  151.  
  152.         }
  153.  
  154.         @Override
  155.         public int hashCode() {
  156.             int result = x;
  157.             result = 31 * result + y;
  158.             return result;
  159.         }
  160.     }
  161.  
  162.     private PrefixTreeNode buildPrefixTree(String[] words) {
  163.         PrefixTreeNode root = new PrefixTreeNode(null, null);
  164.  
  165.         for (String word : words) {
  166.             PrefixTreeNode currentNode = root;
  167.             for (Character c : word.toCharArray()) {
  168.                 if (currentNode.hasChild(c)) {
  169.                     currentNode = currentNode.getChild(c);
  170.                 } else {
  171.                     PrefixTreeNode newNode = new PrefixTreeNode(c, currentNode);
  172.                     currentNode.addChild(c, newNode);
  173.                     currentNode = newNode;
  174.                 }
  175.             }
  176.         }
  177.         return root;
  178.     }
  179. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement