Word II ( word search using Trie data structure)

This article is for self practice 

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

 

Example 1:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Example 2:

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

 

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 12
• board[i][j] is a lowercase English letter.
• 1 <= words.length <= 3 * 104
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.
• All the strings of words are unique.

package practice;

import java.util.*;

class Trie_Node {
    Map<Character, Trie_Node> children = new HashMap<>();
    String word = null;

    public Trie_Node() {
    }
}

public class WordSearchII {
    char[][] _board = null;
    ArrayList<String> list = new ArrayList<>();

    public List<String> findWords(char[][] board, String[] words) {
        Trie_Node root = new Trie_Node();

        // populate dictionary into Trie data structure
        for (String newWord : words) {
            Trie_Node node = root;
            for (int i = 0; i < newWord.length(); i++) {
                Character ch = newWord.charAt(i);
                if (node.children.containsKey(ch)) {
                    node = node.children.get(ch);
                } else {
                    Trie_Node newNode = new Trie_Node();
                    node.children.put(ch, newNode);
                    node = newNode;
                }

            }
            node.word = newWord;
        }

        // Now Search word into Trie Data structure
        this._board = board;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (root.children.containsKey(board[i][j])) {
                    search(i, j, root);
                }
            }
        }
        return this.list;
    }

    private void search(int ro, int co, Trie_Node parent) {
        Character c = this._board[ro][co];
        Trie_Node node = parent.children.get(c);


        if (node.word != null) {
            this.list.add(node.word);
            node.word = null;
        }

        // mark the cell being searched
        this._board[ro][co] = '#';
        int[] rOffeset = {-1, 0, 1, 0};
        int[] cOffset = {0, 1, 0, -1};

        for (int i = 0; i < 4; i++) {
            int row = ro + rOffeset[i];
            int col = co + cOffset[i];
            if (row >= 0 && row < _board.length && col >= 0 && col < _board[0].length) {
                if (node.children.containsKey(_board[row][col])) {
                    search(row, col, node);
                }
            }

        }
        _board[ro][co] = c; // restore the character
        if (node.children.isEmpty()) {
            parent.children.remove(c);
        }
    }

    public static void main(String[] args) {

        char[][] board = {{'o', 'a', 'a', 'n'}, {'e', 't', 'a', 'e'}, {'i', 'h', 'k', 'r'}, {'i', 'f', 'l', 'v'}};
        String[] words = {"oath", "pea", "eat", "rain"};

        WordSearchII wordsearch = new WordSearchII();

        System.out.println(wordsearch.findWords(board, words));

    }


}