Word Search II - rFronteddu/general_wiki GitHub Wiki

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.

class Solution {
    class TrieNode {
        String word;
        boolean isWord;
        HashMap<Character, TrieNode> c = new HashMap<>();
    }
    
    TrieNode root;
    
    public List<String> findWords(char[][] board, String[] words) {
        root = new TrieNode();
        
        for (var word : words) {
            insert (word);
        }

        List<String> result = new ArrayList<>();
        boolean[][] visited = new boolean[board.length][board[0].length];
        
  
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {              
                explore (board, r, c, root, visited, result, words.length);
            }    
        }
        


        return result;
    }
    
    
    void explore (
        char[][] board, 
        int r, int c, 
        TrieNode curr, 
        boolean[][] visited,
        List<String> result,
        int remainingWords) { 
    
        if (curr == null || visited[r][c]) {
            return;
        }
        
        
        char ch = board[r][c];
        curr = curr.c.get(ch);
        if(curr == null) {
            return;
        }

        if (curr.isWord) {
            result.add(curr.word);
            // avoid duplicates
            curr.isWord = false;
            if (--remainingWords == 0) {
                return; // Early termination if all words are found
            }
        }
        
        visited[r][c] = true;
        

        // check up
        if (r-1 >= 0) {
            explore (board, r - 1, c, curr, visited, result, remainingWords);
        }
        
        // check down
        if (r+1 < board.length) {
            explore (board, r + 1, c, curr, visited, result, remainingWords);
        }
      
        // check left
        if (c-1 >= 0) {
            explore (board, r, c - 1, curr, visited, result, remainingWords);
        }
        
        // check right
        if (c+1 < board[0].length) {
            explore (board, r, c + 1, curr, visited, result, remainingWords);
        }
        
        visited[r][c] = false;

    }
    
    void insert (String word) {
        TrieNode curr = root;
        for (var c : word.toCharArray()) {
            if (!curr.c.containsKey(c) ) {
                curr.c.put(c, new TrieNode());
            }
            curr = curr.c.get(c);
        }
        curr.isWord = true;
        curr.word = word;
    }
}
⚠️ **GitHub.com Fallback** ⚠️