Snowflake Interview Question: Word Search in Character Matrix

Problem Description

Given an m by n matrix of characters and a list of strings, 
return the strings that are found in the m by n matrix.

Example:

Matrix:

[
  ['a', 'b', 'c'],
  ['d', 'e', 'f']
]

Words:

['abe', 'xyz', 'abf']

Output:

['abe']

Problem Analysis

Find which words from a list exist in an m x n character matrix. Words are formed by adjacent characters.

Similar to LeetCode Word Search / Word Search II. Typical DFS + Backtracking problem.

Core points:

• Find starting character.
• DFS/BFS to check matching.
• Mark visited cells.
• Pruning is essential.

Solution 2: Trie + DFS (Optimized)

For multiple words, using a Trie (Prefix Tree) significantly optimizes the search.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

class Solution:
    def find_words(self, matrix, words):
        if not matrix or not matrix[0]:
            return []
        
        # 1. Build Trie
        root = TrieNode()
        for word in words:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.word = word
        
        m, n = len(matrix), len(matrix[0])
        result = []
        
        def dfs(i, j, node):
            if node.word:
                result.append(node.word)
                node.word = None  # Avoid duplicates
            
            if i < 0 or i >= m or j < 0 or j >= n:
                return
            
            char = matrix[i][j]
            if char not in node.children:
                return
            
            # Mark visited
            matrix[i][j] = '#'
            
            # Search 4 directions
            for di, dj in [(0,1), (0,-1), (1,0), (-1,0)]:
                dfs(i + di, j + dj, node.children[char])
            
            # Backtrack
            matrix[i][j] = char
            
            # Pruning: remove leaf nodes
            if not node.children[char].children:
                del node.children[char]
        
        # 2. Start DFS from each cell
        for i in range(m):
            for j in range(n):
                if matrix[i][j] in root.children:
                    dfs(i, j, root)
        
        return result

Time Complexity: O(m × n × 4^L) worst case, but much faster in practice due to Trie.

Summary

Snowflake Word Search Matrix Question covers:

1. DFS/BFS Basics: Matrix traversal and path finding.
2. Backtracking: Using and restoring visited state.
3. Trie Optimization: Performance boost for multi-word search.
4. Pruning Strategy: Avoiding unnecessary searches.

oavoservice specializes in interview coaching for Snowflake / Google / Amazon, offering OA support and real-time VO assistance. Contact us if you need help.

Need real interview questions? Contact WeChat Coding0201 immediately to get real questions.