Introduction

In this blog post, we will explore how to solve the LeetCode problem "212" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. 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"] Example 2: Input: board = [["a","b"],["c","d"]], words = ["abcb"] Output: [] Constraints: m == board.length n == board[i].length 1 <= m, n <= 12 board[i][j] is a lowercase English letter. 1 <= words.length <= 3 * 104 1 <= words[i].length <= 10 words[i] consists of lowercase English letters. All the strings of words are unique.

Explanation

• Trie Construction: Build a Trie data structure from the list of words. This allows efficient prefix-based searching.
  • Depth-First Search (DFS): Perform DFS on the board, exploring adjacent cells to find words that exist in the Trie. Backtracking is crucial to avoid revisiting cells within a single word formation.
  • Optimization: Prune the search space by removing words from the Trie as they are found. This avoids redundant searches for already discovered words and significantly improves performance.

• Runtime Complexity: O(m n 4^L), where m and n are the dimensions of the board, and L is the maximum length of a word. In the worst case, we might explore all possible paths on the board up to the maximum word length. Trie lookups are assumed to be O(1). Storage complexity is dominated by the Trie, which is O(sum of lengths of all words).

Code

    class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None  # Store the word if this node represents the end of a word


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.word = word

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.word is not None

    def startsWith(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True


class Solution:
    def findWords(self, board, words):
        trie = Trie()
        for word in words:
            trie.insert(word)

        rows, cols = len(board), len(board[0])
        result = set()

        def dfs(row, col, node):
            if row < 0 or row >= rows or col < 0 or col >= cols or board[row][col] == '#' or board[row][col] not in node.children:
                return

            char = board[row][col]
            node = node.children[char]

            word = node.word
            if word:
                result.add(word)
                node.word = None  # Optimization: Prevent duplicates

            # Mark as visited
            original_char = board[row][col]
            board[row][col] = '#'

            # Explore neighbors
            dfs(row + 1, col, node)
            dfs(row - 1, col, node)
            dfs(row, col + 1, node)
            dfs(row, col - 1, node)

            # Backtrack: Restore original value
            board[row][col] = original_char

        for row in range(rows):
            for col in range(cols):
                dfs(row, col, trie.root)

        return list(result)