added solution for 212 (fishercoder1534#154)

ashmichheda · web-flow · commit e65f15f2ed55 · 2021-03-10T16:41:53.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_212.java b/src/main/java/com/fishercoder/solutions/_212.java
@@ -1,6 +1,7 @@
 package com.fishercoder.solutions;
 
 import java.util.ArrayList;
+import java.util.HashSet;
 import java.util.List;
 
 public class _212 {
@@ -68,4 +69,43 @@ private TrieNode buildTrie(String[] words) {
             return root;
         }
     }
+
+    public static class Solution2 {
+        public List<String> findWords (char[][] board, String[] words) {
+
+            List<String> result = new ArrayList();
+            HashSet<String> set = new HashSet();
+            for (String word : words) {
+                for (int i = 0; i < board.length; i++) {
+                    for (int j = 0; j < board[0].length; j++) {
+                        if (board[i][j] == word.charAt(0) && search(board, i, j, 0, word)) {
+                            set.add(word);
+                        }
+                    }
+                }
+            }
+            result = new ArrayList<>(set);
+            return result;
+        }
+
+        private boolean search(char[][] board, int i, int j, int count, String word) {
+            if (count == word.length()) {
+                return true;
+            }
+
+            if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(count)) {
+                return false;
+            }
+
+            char temp = board[i][j];
+            board[i][j] = ' ';
+
+            boolean foundWord = search(board, i + 1, j, count + 1, word)
+                    || search(board, i - 1, j, count + 1, word)
+                    || search(board, i, j + 1, count + 1, word)
+                    || search(board, i, j - 1, count + 1, word);
+            board[i][j] = temp;
+            return foundWord;
+        }
+    }
 }
