- up until now, all backtracking problems we've encountered were enumeration problems
- this seems to be a **decision-problem**, where we are searching for a feasible solution (checking whether a word can be constructed from a matrix of characters given certain rules)
- constraints:
- words can only be formed by characters that are adjacent to each other (vertically or horizontally neighbouring)
- a brute force appraoch would be a DFS where for every character in the matrix, we recursively check its left,right,up,down neighbours to see if the character in the word matches, each successful recursive call would increment our character of concern.
- we would break if there isnt a match or we are out of bounds
💡 Explanation of Solution
1. Loop through each cell in the board
- if a character matches the first letter of the word, start DFS
2. Recursive DFS function:
- Base Case: if the entire `word` is matched, return true
- Check boundary conditions (out of bouds or character mismatch)
- Mark the cell as visited temporarily to avoid revisiting
- Recursively explore left, right, up, down cells
- Backtrack by unmarking the cell
3. If DFS never finds a word, return false
⌛ Complexity Analysis
Time Complexity: O(4^L)
- L = length of the word
- for each word we explore 4 possible directions
Space Complexity: O(L)
- L max recursive calls on the stack at a given time
💻 Implementation of Solution
class Solution {public: bool exist(vector<vector<char>>& board, string word) { int rows = board.size(), cols = board[0].size(); // Start DFS from each cell for(int i = 0; i < rows; i++) { for(int j = 0; j < cols; j++) { if (dfs(board, i, j, word, 0)) return true; } } return false; } bool dfs(vector<vector<char>>& board, int i, int j, string& word, int wordIndex) { // Base case: If we've matched all characters in `word`, return true if(wordIndex == word.size()) return true; // Out-of-bounds check or character mismatch if(i < 0 || j < 0 || i >= board.size() || j >= board[0].size() || board[i][j] != word[wordIndex]) return false; // Mark cell as visited char temp = board[i][j]; board[i][j] = '#'; // Explore four directions bool found = dfs(board, i-1, j, word, wordIndex+1) || // up dfs(board, i+1, j, word, wordIndex+1) || // down dfs(board, i, j-1, word, wordIndex+1) || // left dfs(board, i, j+1, word, wordIndex+1); // right // Backtrack: Restore original character board[i][j] = temp; return found; }};