🗓 Daily LeetCode Progress – Day 12

[Sascha]

• #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:
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) 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

Источник:

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.