Leet Code 212. Word Search II

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"]

package pep.Day80;

import java.util.LinkedList;
import java.util.List;

public class LeetCode_212_Word_Search_2 {
    public static void main(String[] args) {
        char[][] board = {{'o', 'a', 't', 'h'}, {'e', 't', 'a', 'e'}, {'i', 'h', 'k', 'r'}, {'i', 'f', 'l', 'v'}};

        String[] words = {"oath", "pea", "eat", "rain"};
        System.out.println(findWords(board, words));
    }

    static class Node {
        Node[] children = new Node[26];
        String isEnding = null;
    }

    static Node root = new Node();

    public static void insert(String word) {
        Node current = root;
        for (int i = 0; i < word.length(); i++) {
            char tobeAdded = word.charAt(i);
            if (current.children[tobeAdded - 'a'] == null)
                current.children[tobeAdded - 'a'] = new Node();
            current = current.children[tobeAdded - 'a'];
        }
        current.isEnding = word;
    }

    public static List<String> findWords(char[][] board, String[] words) {
        List<String> ans = new LinkedList<>();
        boolean[][] visited = new boolean[board.length][board[0].length];

        for (String word : words) {
            insert(word);
        }

        // board ko traverse krnege and har baar pouchte rhenge
        // ki iss par traverse krne ka koi fayda hai
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, ans, root, visited);
            }
        }

        return ans;
    }

    private static void dfs(char[][] board, int i, int j, List<String> ans, Node trieNode, boolean[][] visited) {
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || visited[i][j] == true) {
            return;
        }

        Node child = trieNode.children[board[i][j] - 'a'];
        // yha pr do case honge: ya to null value milege ya toh not null

        if (child == null)
            return;

        // word exist krta hai aur woh ending mark kr rha hai
        if (child.isEnding != null) {
            ans.add(child.isEnding);
            // agr do baar cat form ho rha hai to woh nhi hoga
            // humne pehle instance pr hi null daal diya
            child.isEnding = null;
        }

        visited[i][j] = true;
        dfs(board, i - 1, j, ans, child, visited);
        dfs(board, i, j - 1, ans, child, visited);
        dfs(board, i + 1, j, ans, child, visited);
        dfs(board, i, j + 1, ans, child, visited);
        visited[i][j] = false;
    }


}