Word Search in 2D Grid
Problem Statement
Given a 2D board and a list of words, check which words exist in the board using trie + DFS.
Example: Board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], Words = ["oath","pea"] → ["oath"]
Approach: Trie + DFS Backtracking
Explanation: Insert words into trie. DFS on grid, mark visited, check trie path.
Time Complexity: O(M*N*4^L), M,N = grid size, L = max word length
Space Complexity: O(N*L) for trie