🗓 Daily LeetCode Progress – Day 12

Problems Solved:

#79 Word Search
#70 Climbing Stairs

This continues my daily series (Day 12: Backtracking + DP). Today I focused on two classics: exploring a grid with depth-first search and backtracking, and computing Fibonacci-style counts with constant-space dynamic programming.

💡 What I Learned

For Word Search, the key is DFS with backtracking. At each step, mark the current cell as visited, recursively explore neighbors, and then restore the cell. This prevents reusing the same cell in the same path.
For Climbing Stairs, it’s essentially the Fibonacci sequence. The number of ways to reach step n is the sum of the ways to reach (n-1) and (n-2). Using just two variables makes the solution O(1) space.
Both problems emphasize incremental correctness: Word Search prunes invalid paths early, and Climbing Stairs builds from smaller subproblems.

🧩 #79 — Word Search

Python (DFS + Backtracking)

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        def dfs(r, c, i) -> bool:
            if i == len(word):
                return True
            if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[i]:
                return False
            temp = board[r][c]
            board[r][c] = '#'
            found = (
                dfs(r+1, c, i+1) or
                dfs(r-1, c, i+1) or
                dfs(r, c+1, i+1) or
                dfs(r, c-1, i+1)
            )
            board[r][c] = temp
            return found
        for r in range(m):
            for c in range(n):
                if dfs(r, c, 0):
                    return True
        return False

C++ (DFS + Backtracking)

using namespace std;

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        vector<pair<int,int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};

        function<bool(int,int,int)> dfs = [&](int r, int c, int i) {
            if (i == word.size()) return true;
            if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word[i]) return false;
            char tmp = board[r][c];
            board[r][c] = '#';
            for (auto [dr, dc] : dirs) {
                if (dfs(r+dr, c+dc, i+1)) {
                    board[r][c] = tmp;
                    return true;
                }
            }
            board[r][c] = tmp;
            return false;
        };

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (dfs(r, c, 0)) return true;
            }
        }
        return false;
    }
};

Why it works: by marking visited cells and restoring them, each path explores unique positions without overlap.

Time: O(m * n * 4^L) where L = length of word
Space: O(L) recursion depth

🧩 #70 — Climbing Stairs

Python (DP with O(1) space)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        a, b = 1, 2
        for _ in range(3, n+1):
            a, b = b, a+b
        return b

C++ (DP with O(1) space)

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int a = 1, b = 2;
        for (int i = 3; i <= n; ++i) {
            int c = a;
            a = b;
            b = c + b;
        }
        return b;
    }
};

Why it works: each step’s ways depend only on the previous two steps.

Time: O(n)
Space: O(1)

📸 Achievements

Word Search (Python & C++)

Climbing Stairs (Python & C++)

📦 Complexity Recap

Word Search: exponential in word length, prunes invalid paths early.
Climbing Stairs: linear time, constant space.

📣 Join the Journey

I’m solving and documenting problems daily in both Python and C++, highlighting recursion, DP, and algorithmic reasoning. Follow along if you’re into problem solving and system design thinking.

Links