Advertisement
Guest User

Untitled

a guest
Aug 22nd, 2019
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.43 KB | None | 0 0
  1. class Solution {
  2.     class Node{
  3.         Character c;
  4.         Map<Character, Node> children;
  5.         boolean isLeaf;
  6.        
  7.         public Node(){
  8.             children = new HashMap<>();
  9.         }
  10.  
  11.         void addChild(Character c){
  12.             Node node = new Node();
  13.             node.c = c;
  14.             children.put(c, node);
  15.         }
  16.     }
  17.    
  18.     class Trie {
  19.         Node root;
  20.         /** Initialize your data structure here. */
  21.         public Trie() {
  22.             root = new Node();
  23.         }
  24.  
  25.         private void insert(String word, int i, Node node){
  26.             if(i == word.length()){
  27.                 node.isLeaf = true;
  28.                 return;
  29.             }
  30.             Character c = word.charAt(i);
  31.             if(!node.children.containsKey(c)){
  32.                 node.addChild(c);
  33.             }
  34.             insert(word, i+1, node.children.get(c));
  35.         }
  36.  
  37.         /** Inserts a word into the trie. */
  38.         public void insert(String word) {
  39.             insert(word, 0, root);
  40.         }
  41.     }
  42.    
  43.     char[][] board;
  44.     boolean[][] visited;
  45.    
  46.     public void dfs(int i, int j, List<String> res, String wordSoFar, Node node){
  47.         if(node.isLeaf){
  48.             res.add(wordSoFar);
  49.             node.isLeaf = false;
  50.             // return;
  51.         }
  52.        
  53.         if(i < 0 || j < 0 ||
  54.            i == board.length || j==board[0].length ||
  55.            visited[i][j] || !node.children.containsKey(board[i][j]))
  56.             return;
  57.        
  58.         char ch = board[i][j];
  59.         visited[i][j] = true;
  60.         dfs(i-1, j, res, wordSoFar+ch, node.children.get(ch) );
  61.         dfs(i, j-1, res, wordSoFar+ch, node.children.get(ch) );
  62.         dfs(i+1, j, res, wordSoFar+ch, node.children.get(ch) );
  63.         dfs(i, j+1, res, wordSoFar+ch, node.children.get(ch) );
  64.        
  65.         visited[i][j] = false;
  66.        
  67.     }
  68.    
  69.     public List<String> findWords(char[][] board, String[] words) {
  70.         Trie trie = new Trie();
  71.         for(int i=0; i<words.length; i++){
  72.             trie.insert(words[i]);
  73.         }
  74.         List<String> resList = new ArrayList<>();
  75.         this.board = board;
  76.         this.visited = new boolean[board.length][board[0].length];
  77.         for(int i=0; i<board.length; i++){
  78.             for(int j=0; j<board[0].length; j++){
  79.                 dfs(i,j,resList,"",trie.root);
  80.             }
  81.         }
  82.         Collections.sort(resList);
  83.         return resList;
  84.     }
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement