Update Word Search II.java

varunu28 · web-flow · commit 6843b57e8f15 · 2021-10-09T07:40:36.000-05:00
diff --git a/Hard/Word Search II.java b/Hard/Word Search II.java
@@ -1,66 +1,62 @@
 class Solution {
-    public List<String> findWords(char[][] board, String[] words) {
-        List<String> result = new ArrayList<>();
-        TrieNode root = buildTrie(words);
-
-        for (int i = 0; i < board.length; i++) {
-            for (int j = 0; j < board[0].length; j++) {
-                helper(board, i, j, root, result);
-            }
-        }
-
-        return result;
+  public List<String> findWords(char[][] board, String[] words) {
+    List<String> result = new ArrayList<>();
+    TrieNode root = buildTrie(words);
+    for (int i = 0; i < board.length; i++) {
+      for (int j = 0; j < board[0].length; j++) {
+        dfs(board, i, j, result, root);
+      }
     }
-
-    private void helper(char[][] board, int i, int j, TrieNode root, List<String> result) {
-        if (i < 0 || i >= board.length || j >= board[i].length || j < 0) {
-            return;
-        }
-
-        char c = board[i][j];
-        if (c == '@' || root.next[c - 'a'] == null) {
-            return;
-        }
-
-        root = root.next[c - 'a'];
-        if (root.word != null) {
-            result.add(root.word);
-            root.word = null;
+    return result;
+  }
+  
+  private TrieNode buildTrie(String[] words) {
+    TrieNode root = new TrieNode();
+    for (String word : words) {
+      TrieNode temp = root;
+      for (char c : word.toCharArray()) {
+        if (temp.children[c - 'a'] == null) {
+          temp.children[c - 'a'] = new TrieNode();
         }
-
-        // Choose
-        board[i][j] = '@';
-
-        // Explore
-        helper(board, i + 1, j, root, result);
-        helper(board, i, j + 1, root, result);
-        helper(board, i, j - 1, root, result);
-        helper(board, i - 1, j, root, result);
-
-        // Un-choose
-        board[i][j] = c;
+        temp = temp.children[c - 'a'];
+     }
+       temp.word = word;
     }
+    return root;
+  }
 
-    private TrieNode buildTrie(String[] words) {
-        TrieNode root = new TrieNode();
-        for (String word : words) {
-            TrieNode temp =root;
-            for (char c : word.toCharArray()) {
-                if (temp.next[c - 'a'] == null) {
-                    temp.next[c - 'a'] = new TrieNode();
-                }
-
-                temp = temp.next[c - 'a'];
-            }
-
-            temp.word = word;
-        }
-
-        return root;
+  private void dfs(char[][] board, int i, int j, List<String> result, TrieNode root) {
+    char c = board[i][j];
+    if (c == '#' || root.children[c - 'a'] == null) {
+      return;
     }
-
-    class TrieNode {
-        TrieNode[] next = new TrieNode[26];
-        String word;
+    root = root.children[c - 'a'];
+    if (root.word != null) {
+      result.add(root.word);
+      root.word = null;
+    }
+    board[i][j] = '#';
+    triggerDfsIfValid(board, i, j, result, root);
+    board[i][j] = c;
+  }
+  
+  private void triggerDfsIfValid(char[][] board, int i, int j, List<String> result, TrieNode root) {
+    if (i > 0) {
+      dfs(board, i - 1, j, result, root);
+    }
+    if (j > 0) {
+      dfs(board, i, j - 1, result, root);
+    }
+    if (i < board.length - 1) {
+      dfs(board, i + 1, j, result, root);
+    }
+    if (j < board[0].length - 1) {
+      dfs(board, i, j + 1, result, root);
     }
+  }
+  
+  class TrieNode {
+    TrieNode[] children = new TrieNode[26];
+    String word;
+  }
 }
