package Graphs;

import java.util.*;

class BoggleBoard {
    public static List<String> boggleBoard(char[][] board, String[] words) {
        // Create a Trie data structure to store the words to be searched
        Trie trie = new Trie();
        for (String word : words) {
            trie.addWord(word);
        }

        Set<String> foundWords = new HashSet<>();
        boolean[][] visited = new boolean[board.length][board[0].length];
        // Execute depth-first search for each position on the board
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                search(i, j, board, trie.root, visited, foundWords);
            }
        }
        return new ArrayList<String>(foundWords);
    }

    // Recursive function for depth-first search
    private static void search(int i, int j, char[][] board, TrieNode node, boolean[][] visited, Set<String> foundWords) {
        // Check if the current position has already been visited
        if (visited[i][j]) {
            return;
        }
        char letter = board[i][j];
        // If the prefix of the word does not exist in the Trie, return directly
        if (!node.children.containsKey(letter)) {
            return;
        }
        // Mark the current position as visited
        visited[i][j] = true;
        // Move the current node to the next position
        node = node.children.get(letter);
        // If the current node is the end of a word, add the word to the result set
        if (node.isWord) {
            foundWords.add(node.word);
        }
        // Recursively visit the adjacent 8 positions
        for (int row = i - 1; row <= i + 1 && row < board.length; row++) {
            for (int col = j - 1; col <= j + 1 && col < board[0].length; col++) {
                if (row >= 0 && col >= 0) {
                    search(row, col, board, node, visited, foundWords);
                }
            }
        }
        // Mark the current position as unvisited
        visited[i][j] = false;
    }
  
	public static void main(String[] args) {
        char[][] board = {
                {'t', 'h', 'i', 's', 'i', 's', 'a'},
                {'s', 'i', 'm', 'p', 'l', 'e', 'x'},
                {'b', 'x', 'x', 'x', 'x', 'e', 'b'},
                {'x', 'o', 'g', 'g', '1', 'x', 'o'},
                {'x', 'x', 'x', 'D', 'T', 'r', 'a'},
                {'R', 'E', 'P', 'E', 'A', 'd', 'x'},
                {'x', 'x', 'x', 'x', 'x', 'x', 'x'},
                {'N', 'O', 'T', 'R', 'E', '-', 'P'},
                {'x', 'x', 'D', 'E', 'T', 'A', 'E'},
        };
        String[] words = {"thisisa","tsbxxRxNx","this", "is", "not", "a", "simple", "boggle", "board", "test", "REPEATED", "NOTRE-PEATED"};
        List<String> result = boggleBoard(board, words);
        System.out.println(result);

    }
}

/**
 * Trie tree node
 */
class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isWord = false;
    String word = "";
}

/**
 * Trie tree
 */
class Trie {
    TrieNode root = new TrieNode();

    // Add a word to the Trie tree
    public void addWord(String word) {
        TrieNode node = root;
        for (char letter : word.toCharArray()) {
            if (!node.children.containsKey(letter)) {
                node.children.put(letter, new TrieNode());
            }
            node = node.children.get(letter);
        }
        node.isWord = true;
        node.word = word;
    }
}

package Graphs;

import com.sun.deploy.util.StringUtils;

import java.util.*;

/**
 * @author zhengstars
 * @date 2023/03/24
 */

/**
 * Main idea：
 *
 * 1. Build a trie to store all the words in the dictionary.
 *
 * 2. For each grid, search for words starting with the character of this grid on the trie,
 * use DFS to search the adjacent grids in the eight directions of up, down, left, right, and diagonals,
 * recursively search until reaching a node that does not exist in the trie, and return to the previous grid to continue the search.
 *
 *
 * - Time complexity: Assuming the average length of all words in the dictionary is L and the size of the matrix is M x N,
 * the time complexity is O(MNL + 8MN), where O(MNL) is the time complexity for building the trie,
 * and O(8MN) is the time complexity for performing DFS for each grid.
 *
 * - Space complexity: The space complexity of the trie is O(SL), where S is the number of words and L is the average length of words.
 * The space occupied by visited array is O (MN). Therefore, the total space complexity is O (SL + MN).
 */

public class BoggleBoard3 {
    public static List<String> boggleBoard(char[][] board, String[] words) {
        // Build a trie data structure to store the given words
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            // Traverse the word and add each character to the trie
            for (char c : word.toCharArray()) {
                if (!node.children.containsKey(c)) {
                    node.children.put(c, new TrieNode());
                }
                node = node.children.get(c);
            }
            // Mark the last node as a word node
            node.word = word;
        }

        // Use DFS to search for valid words on the board
        Set<String> result = new HashSet<String>();
        int row = board.length;
        int col = board[0].length;
        boolean[][] visited = new boolean[row][col];

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                dfs(board, visited, i, j, root, result);
            }
        }
        // Convert the result set to a list and return it
        return new ArrayList<String>(result);
    }

    private static void dfs(char[][] board, boolean[][] visited, int i, int j, TrieNode node, Set<String> result) {
        char c = board[i][j];
        // Check if the current character exists in the trie
        if (!node.children.containsKey(c)) {
            return;
        }

        // Mark the current cell as visited and move to the next node in the trie
        visited[i][j] = true;
        node = node.children.get(c);

        // Check if the current node is a word node and add it to the result set
        if (!node.word.isEmpty()) {
            result.add(node.word);
        }

        // Define the possible directions for the next move on the board
        int[][] directions = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {-1, -1}, {-1, 1}, {1, -1}};

        // Recursively search for valid words in each direction
        for (int[] dir : directions) {
            int x = i + dir[0];
            int y = j + dir[1];

            // Check if the next cell is out of bounds or already visited
            if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || visited[x][y]) {
                continue;
            }
            dfs(board, visited, x, y, node, result);
        }

        // Mark the current cell as unvisited before backtracking
        visited[i][j] = false;
    }

    public static void main(String[] args) {
        char[][] board = {
                {'t', 'h', 'i', 's', 'i', 's', 'a'},
                {'s', 'i', 'm', 'p', 'l', 'e', 'x'},
                {'b', 'x', 'x', 'x', 'x', 'e', 'b'},
                {'x', 'o', 'g', 'g', '1', 'x', 'o'},
                {'x', 'x', 'x', 'D', 'T', 'r', 'a'},
                {'R', 'E', 'P', 'E', 'A', 'd', 'x'},
                {'x', 'x', 'x', 'x', 'x', 'x', 'x'},
                {'N', 'O', 'T', 'R', 'E', '-', 'P'},
                {'x', 'x', 'D', 'E', 'T', 'A', 'E'},
        };
        String[] words = {"thisisa","tsbxxRxNx","this", "is", "not", "a", "simple", "boggle", "board", "test", "REPEATED", "NOTRE-PEATED"};
        List<String> result = boggleBoard(board, words);
        System.out.println(result);

    }
}