Backtracking
Letter Combinations of a Phone Number (Medium)
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
# 1(---) 2(abc) 3(def) # 4(ghi) 5(jkl) 6(mno) # 7(pqrs) 8(tuv) 9(wxyz)
def letterCombinations(digits: str) -> List[str]: m = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz" } answer = [] def dfs(i, currStrList): if i == len(digits): answer.append("".join(currStrList)) return for char in m[digits[i]]: currStrList.append(char) dfs(i + 1, currStrList) currStrList.pop() dfs(0, []) return answer
Time: O(n * 4n), n = digits length
Space: O(n * 4n) or O(n) excluding output
Alternative solution:
from collections import deque def letterCombinations(digits: str) -> List[str]: if not digits: return [] m = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz" } queue = deque([""]) # BFS, building strings until matching string length while len(queue[0]) != len(digits): curr = queue.popleft() for char in m[digits[len(curr)]]: queue.append(curr + char) return list(queue)
Time: O(n * 4n)
Space: O(n * 4n)
Combinations (Medium)
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
You may return the answer in any order.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
def combine(n: int, k: int) -> List[List[int]]: answer = [] # DFS adding only larger values per level def dfs(currVal, currLi): if len(currLi) == k: answer.append(currLi[:]) return # Optimization from range(currVal, n + 1) # Skip recursion if not enough numbers left # Example: n = 10, k = 5, currLi = [], currVal = 7 # len([7, 8, 9, 10]) < k for val in range(currVal, n - (k - len(currLi)) + 2): currLi.append(val) dfs(val + 1, currLi) currLi.pop() dfs(1, []) return answer
Time: O(c(n, k) * k)
Space: O(c(n, k) * k) or O(k) excluding output
Permutations (Medium)
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
def permute(nums: List[int]) -> List[List[int]]: answer, visited = [], set([None]) def dfs(currVal, currLi): if len(currLi) == len(nums): answer.append(currLi[:]) return for val in nums: # Tracking visited values only works if values are unique # Track index instead if duplicate values if val in visited: continue currLi.append(val) visited.add(val) dfs(val, currLi) currLi.pop() visited.remove(val) dfs(None, []) return answer
Time: O(n * n!)
Space: O(n * n!) or O(n) exluding output
Combination Sum (Medium)
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
def combinationSum(candidates: List[int], target: int) -> List[List[int]]: candidates.sort() answer = [] def dfs(index, currLi, currSum): if currSum == target: answer.append(currLi[:]) return for i in range(index, len(candidates)): # Done checking because all further values are greater if candidates[i] + currSum > target: break currLi.append(candidates[i]) # Pass i instead of i + 1 because duplicates allowed dfs(i, currLi, currSum + candidates[i]) currLi.pop() dfs(0, [], 0) return answer
Time: O(nt / m), n = len(candidates), t = target, m = min(candidates)
Space: O(k * t / m + t / m) or O(t / m) excluding output, k = number of valid combinations
Generate Parentheses (Medium)
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
def generateParenthesis(n: int) -> List[str]: answer, li = [], [] def dfs(openCount, closeCount): if openCount == closeCount == n: answer.append("".join(li)) return if openCount < n: li.append("(") dfs(openCount + 1, closeCount) li.pop() if closeCount < openCount: li.append(")") dfs(openCount, closeCount + 1) li.pop() dfs(0, 0) return answer
Time: O(2n)
Space: O(n)
Word Search (Medium)
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
def exist(board: List[List[str]], word: str) -> bool: ROWS, COLS = len(board), len(board[0]) directions = [(-1, 0), (0, 1), (1, 0), (0, -1)] # Can optimize by preprocessing input # Create frequency map of board and word, compare and exit early def dfs(index, row, col): if not 0 <= row < ROWS or not 0 <= col < COLS or board[row][col] != word[index]: return False if index == len(word) - 1: return True # Mark as visited char = board[row][col] board[row][col] = "" for r, c in directions: if dfs(index + 1, row + r, col + c): return True board[row][col] = char return False for row in range(len(board)): for col in range(len(board[0])): if board[row][col] == word[0] and dfs(0, row, col): return True return False
Time: O(m _ n _ 3L), L = word length
Space: O(L)