LeetCode 212: Word Search II Solution

Master LeetCode problem 212 (Word Search II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

212. Word Search II

Hard

Array String Backtracking Trie Matrix

Problem Explanation

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.

Build a Trie from the given list of words.
Traverse the board and for each cell, check if the current character is in the Trie.
If it is, perform DFS starting from that cell to check if we can form any word present in the Trie.
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.

Solution Code

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;
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 212 (Word Search II)?

This page provides optimized solutions for LeetCode problem 212 (Word Search II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 212 (Word Search II)?

The time complexity for LeetCode 212 (Word Search II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 212 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 212 in Java, C++, or Python.

Back to LeetCode Solutions