Check if Word Can Be Placed In Crossword LeetCode solution in Java

1
class Solution {
2
  public boolean placeWordInCrossword(char[][] board, String word) {
3
    String curr = "";
4

5
    Trie trie = new Trie();
6

7
    // Insert all horizontal strings
8
    for (int i = 0; i < board.length; i++) {
9
      for (int j = 0; j < board[0].length; j++) {
10
        if (board[i][j] == '#') {
11
          insertIntoTrie(trie, curr);
12
          curr = "";
13
        } else {
14
          curr += board[i][j];
15
        }
16
      }
17
      insertIntoTrie(trie, curr);
18
      curr = "";
19
    }
20

21
    // Insert all vertical strings
22
    for (int i = 0; i < board[0].length; i++) {
23
      for (int j = 0; j < board.length; j++) {
24
        if (board[j][i] == '#') {
25
          insertIntoTrie(trie, curr);
26
          curr = "";
27
        } else {
28
          curr += board[j][i];
29
        }
30
      }
31
      insertIntoTrie(trie, curr);
32
      curr = "";
33
    }
34

35
    return trie.isPresent(word);
36
  }
37

38
  // Insert string and reverse of string into the trie
39
  private void insertIntoTrie(Trie trie, String s) {
40
    trie.insert(s);
41
    StringBuilder sb = new StringBuilder(s);
42
    sb.reverse();
43
    trie.insert(sb.toString());
44
  }
45

46
  class TrieNode {
47
    Map<Character, TrieNode> children;
48
    boolean isEnd;
49

50
    TrieNode() {
51
      children = new HashMap<>();
52
      isEnd = false;
53
    }
54
  }
55

56
  class Trie {
57
    TrieNode root;
58

59
    Trie() {
60
      root = new TrieNode();
61
    }
62

63
    void insert(String s) {
64
      TrieNode curr = root;
65

66
      for (int i = 0; i < s.length(); i++) {
67
        char c = s.charAt(i);
68
        if (!curr.children.containsKey(c)) {
69
          curr.children.put(c, new TrieNode());
70
        }
71

72
        curr = curr.children.get(c);
73
      }
74

75
      curr.isEnd = true;
76
    }
77

78
    boolean isPresent(String key) {
79
      TrieNode curr = root;
80
      return helper(key, 0, root);
81
    }
82

83
    boolean helper(String key, int i, TrieNode curr) {
84
      if (curr == null) return false;
85

86
      if (i == key.length()) return curr.isEnd;
87

88
      char c = key.charAt(i);
89
      return helper(key, i + 1, curr.children.get(c)) || helper(key, i + 1, curr.children.get(' '));
90
    }
91
  }
92
}