DevExCode

LeetCode 212: Word Search II

ArrayStringBacktrackingTrieMatrix

Problem Description

Explanation:

To solve this problem, we can use a Trie data structure to store all the words from the input list words. Then, we perform a Depth First Search (DFS) on the board starting from each cell to search for words that are present in the Trie.

  1. Build a Trie from the given list of words.
  2. Traverse the board and for each cell, check if the current character is in the Trie.
  3. If it is, perform DFS starting from that cell to check if we can form any word present in the Trie.
  4. Keep track of visited cells and backtrack when necessary.

Time Complexity: Let m be the number of rows in the board and n be the number of columns. Building the Trie takes O(words * avg_word_length) time. The DFS on the board takes O(m * n * 4^l) time, where l is the maximum length of a word in the Trie.

Space Complexity: The Trie will take O(words * avg_word_length) space, and the DFS recursion stack will take O(m * n) space.

:

View on LeetCode

Solutions

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, trie.root, result);
            }
        }
        
        return result;
    }
    
    private void dfs(char[][] board, int i, int j, TrieNode node, List<String> result) {
        char c = board[i][j];
        if (c == '#' || node.children[c - 'a'] == null) {
            return;
        }
        
        node = node.children[c - 'a'];
        if (node.word != null) {
            result.add(node.word);
            node.word = null; // avoid duplicates
        }
        
        board[i][j] = '#'; // mark as visited
        
        if (i > 0) dfs(board, i - 1, j, node, result);
        if (j > 0) dfs(board, i, j - 1, node, result);
        if (i < board.length - 1) dfs(board, i + 1, j, node, result);
        if (j < board[0].length - 1) dfs(board, i, j + 1, node, result);
        
        board[i][j] = c; // backtrack
    }
    
    class Trie {
        TrieNode root;
        
        public Trie() {
            root = new TrieNode();
        }
        
        public void insert(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                if (node.children[c - 'a'] == null) {
                    node.children[c - 'a'] = new TrieNode();
                }
                node = node.children[c - 'a'];
            }
            node.word = word;
        }
    }
    
    class TrieNode {
        TrieNode[] children;
        String word;
        
        public TrieNode() {
            children = new TrieNode[26];
            word = null;
        }
    }
}

Related LeetCode Problems

Previous ProblemNext Problem

Loading editor...