Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- class Node{
- Character c;
- Map<Character, Node> children;
- boolean isLeaf;
- public Node(){
- children = new HashMap<>();
- }
- void addChild(Character c){
- Node node = new Node();
- node.c = c;
- children.put(c, node);
- }
- }
- class Trie {
- Node root;
- /** Initialize your data structure here. */
- public Trie() {
- root = new Node();
- }
- private void insert(String word, int i, Node node){
- if(i == word.length()){
- node.isLeaf = true;
- return;
- }
- Character c = word.charAt(i);
- if(!node.children.containsKey(c)){
- node.addChild(c);
- }
- insert(word, i+1, node.children.get(c));
- }
- /** Inserts a word into the trie. */
- public void insert(String word) {
- insert(word, 0, root);
- }
- }
- char[][] board;
- boolean[][] visited;
- public void dfs(int i, int j, List<String> res, String wordSoFar, Node node){
- if(node.isLeaf){
- res.add(wordSoFar);
- node.isLeaf = false;
- // return;
- }
- if(i < 0 || j < 0 ||
- i == board.length || j==board[0].length ||
- visited[i][j] || !node.children.containsKey(board[i][j]))
- return;
- char ch = board[i][j];
- visited[i][j] = true;
- dfs(i-1, j, res, wordSoFar+ch, node.children.get(ch) );
- dfs(i, j-1, res, wordSoFar+ch, node.children.get(ch) );
- dfs(i+1, j, res, wordSoFar+ch, node.children.get(ch) );
- dfs(i, j+1, res, wordSoFar+ch, node.children.get(ch) );
- visited[i][j] = false;
- }
- public List<String> findWords(char[][] board, String[] words) {
- Trie trie = new Trie();
- for(int i=0; i<words.length; i++){
- trie.insert(words[i]);
- }
- List<String> resList = new ArrayList<>();
- this.board = board;
- this.visited = new boolean[board.length][board[0].length];
- for(int i=0; i<board.length; i++){
- for(int j=0; j<board[0].length; j++){
- dfs(i,j,resList,"",trie.root);
- }
- }
- Collections.sort(resList);
- return resList;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement