Backtracking Flashcards
- Generate Parentheses
Solved
Medium
Topics
Companies Amazon
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
Example 2:
Input: n = 1
Output: [”()”]
Constraints:
1 <= n <= 8
https://leetcode.com/problems/generate-parentheses/description/
Trick: Add open when you can, add closed when you can
We do not need to pop stuff as we do not modify the original value, we just send a modified version to the next call.
class Solution(object):
def generateParenthesis(self, n):
“””
:type n: int
:rtype: List[str]
“””
ret = []
def rec(val, numopen, numclosed):
if numopen == numclosed == n:
ret.append(““.join(val))
return
if numopen < n:
rec(val + ['('], numopen+1, numclosed)
if numclosed < numopen:
rec(val + [')'], numopen, numclosed+1)
rec([], 0, 0)
return ret
- Subsets
Medium
Given an integer array nums of unique elements, return all possible
subsets
(the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
Constraints:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique.
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
output = [[]]
for num in nums:
output += [cur + [num] for cur in output]
return output
Backtracking
~~~
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
subsets = []
def dfs(i):
if i >= len(nums):
res.append(subsets.copy())
return
subsets.append(nums[i])
dfs(i+1)
subsets.pop()
dfs(i+1)
dfs(0)
return res ~~~
- 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.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1
Output: []
Constraints:
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40
https://leetcode.com/problems/combination-sum/description/
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
output = []
def rec(nums, idx):
if nums and sum(nums) == target:
output.append(nums[:])
return
if (idx == len(candidates)) or (nums and sum(nums) > target):
return
rec([candidates[idx]] + nums, idx)
rec(nums, idx + 1)
rec([], 0)
return output- Permutations
Medium
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1]
Output: [[1]]
Constraints:
1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.
https://leetcode.com/problems/permutations/description/
Note the use of Set here, otherwise for each call we have to do n operations.
~~~
class Solution(object):
def permute(self, nums):
“””
:type nums: List[int]
:rtype: List[List[int]]
“””
output = []
seen = set()
def rec(perms):
if len(perms) == len(nums):
output.append(perms[:])
return
for num in nums:
if num not in seen:
seen.add(num)
rec([num] + perms)
seen.remove(num)
rec([])
return output ```
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
output = [[]]
for n in nums:
temp = []
for p in output:
for i in range(len(p)+1):
temp.append(p[:i] + [n] + p[i:])
output = temp
return output
- Permutations II
Solved
Medium
Topics
Companies
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Example 1:
Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]
Example 2:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Constraints:
1 <= nums.length <= 8
-10 <= nums[i] <= 10
https://leetcode.com/problems/permutations-ii/description/
https://leetcode.com/problems/permutations-ii/description/
Without Sorting - DFS
We maintain a pos dict that stores the numbers that have been seen in the current position, thus we can ignore same elements being repeated. You can also use a set that is created in each loop.
from collections import defaultdict, Counter
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
pos_occurance = defaultdict(set)
used = set()
ret = []
def gen_perms(perm, pos):
if pos == len(nums):
ret.append(perm[:])
return
for i in range(len(nums)):
if nums[i] not in pos_occurance[pos] and i not in used:
pos_occurance[pos].add(nums[i])
used.add(i)
gen_perms(perm+[nums[i]], pos+1)
used.remove(i)
pos_occurance[pos] = set()
gen_perms([], 0)
return ret
With Sorting
~~~
from collections import Counter
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
output = []
counts = Counter(nums)
def rec(perms):
if len(perms) == len(nums):
output.append(perms[:])
return
# Use the unique nums to iterate. This way you accurately track if its been used or not.
for num in counts.keys():
if counts[num]:
counts[num] -= 1
rec([num] + perms)
counts[num] += 1
rec([])
return output ~~~
- Subsets II
Solved
Medium
Topics
Companies
Given an integer array nums that may contain duplicates, return all possible
subsets
(the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
Constraints:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
https://leetcode.com/problems/subsets-ii/description/
The non sort does the same thing, if we notice, we do not make a call without the number if it’s already in the set.
We know that if it’s already in the set, the first occurance, will make the call without itself.
This will make sure to include all subsets.
~~~
et 1123
1 1 2 3
1 1 2
1 1 3
1 2– skip this chain as it will be repeated later.
1
1 2 3 - here is the chain we skipped earlier.
1 2
1 3
1
2 3
2
3
~~~
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
output = []
def rec(subsets, idx):
if idx == len(nums):
output.append(subsets[:])
return
rec([nums[idx]] + subsets, idx + 1)
if nums[idx] not in subsets:
rec(subsets, idx + 1)
rec([], 0)
return output
Other way is to sort the nums and if the previous is the same, skip.
add subsets so far each iteration to the output.
Each call go over the all the nums from idx to len(nums) where idx is incremented for each call.
Only the first non dup number will be used if its not the first time using it (i != idx)
eg.
~~~
1123
for ease of example first 1 is 1a and secondis 1b
1a
1a 1b
1a 1b 2
1a 1b 2 3
1a 1b 3
1a 1b
1a 2
1a 2 3
1a 3
1b - Skip as 1b is not idx (0) and its == 1a (i-1 loc)
2 3
2
3
~~~
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
output = []
nums.sort()
def rec(subsets, idx):
output.append(subsets[:])
if idx == len(nums):
return
for i in range(idx, len(nums)):
if i != idx and nums[i-1] == nums[i]:
continue
rec(subsets + [nums[i]], i+1)
rec([], 0)
return output
- Word Search
Solved
Medium
Topics
Companies
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.
Example 1:
Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”
Output: true
Example 2:
Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “SEE”
Output: true
Example 3:
Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCB”
Output: false
Constraints:
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.
Follow up: Could you use search pruning to make your solution faster with a larger board?
https://leetcode.com/problems/word-search/
from collections import deque, Counter
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
movements = [[0,1], [-1,0], [1,0], [0,-1]]
seen = set()
rows = len(board)
cols = len(board[0])
# If matrix smaller than word
if rows * cols < len(word):
return False
chars = {c for row in board for c in row}
# If board does not have all the characters in the word
if not chars.issuperset(set(word)):
return False
# if the board char counts are not same as word's char count
board_counts = Counter(c for row in board for c in row)
counts_word = Counter(word)
if not counts_word <= board_counts:
return False
word = word if counts_word[word[0]] < counts_word[word[-1]] else word[::-1]
def dfs(ri, ci, word):
if not word:
return True
seen.add((ri,ci))
for rm, cm in movements:
rn, cn = ri + rm, ci + cm
if rn in range(rows) and cn in range(cols) and board[rn][cn] == word[0] and (rn, cn) not in seen:
found = dfs(rn, cn, word[1:])
if found:
return True
seen.remove((ri, ci))
return False
for r in range(rows):
for c in range(cols):
if board[r][c] == word[0]:
found = dfs(r,c, word[1:])
if found:
return True- Palindrome Partitioning
Medium
Given a string s, partition s such that every
substring
of the partition is a
palindrome
. Return all possible palindrome partitioning of s.
Example 1:
Input: s = “aab”
Output: [[“a”,”a”,”b”],[“aa”,”b”]]
Example 2:
Input: s = “a”
Output: [[“a”]]
Constraints:
1 <= s.length <= 16 s contains only lowercase English letters.
https://leetcode.com/problems/palindrome-partitioning/description/
https://leetcode.com/problems/palindrome-partitioning/description/
class Solution:
def partition(self, s: str) -> List[List[str]]:
output = []
# Slower
def _isPalindrome(word):
l = 0
r = len(word) - 1
while l < r:
if word[l] != word[r]:
return False
l+=1
r-=1
return True
# This is faster, possibly optimized by python.
def isPalindrome(word):
return word == word[::-1]
def rec(i, palins):
if i == len(s):
output.append(palins[:])
return
for idx in range(i, len(s)):
if isPalindrome(s[i:idx+1]):
rec(idx+1, palins + [s[i:idx+1]])
rec(0, [])
return output
Using Dynamic Programming
Using Memoization + DP (fastest) saves results at every index + reduces time to check for palindrome
from functools import cache
class Solution:
def partition(self, s: str) -> List[List[str]]:
output = []
dp = [[False] * len(s) for _ in range(len(s))]
def isPalin(start, end):
return start == end or (s[start] == s[end] and (end-start<2 or dp[start+1][end-1]))
@cache
def backtrack(i):
if i == len(s):
return -1
out = []
for idx in range(i+1, len(s)+1):
if isPalin(i, idx-1):
consider = [s[i:idx]]
dp[i][idx-1] = True
res = backtrack(idx)
if not res:
return []
elif res == -1:
out.append([s[i:idx]])
else:
for p in res:
out.append(consider + p)
return out
return backtrack(0)
DP
~~~
class Solution:
def partition(self, s):
res = []
dp = [[False] * len(s) for _ in range(len(s))]
def dfs(pals, start):
if start >= len(s):
res.append(pals[:])
return
for end in range(start, len(s)):
if s[start] == s[end] and (end-start <= 2 or dp[start+1][end-1]):
dp[start][end] = True
dfs(pals + [s[start:end+1]], end+1)
dfs([], 0)
return res ~~~
- Letter Combinations of a Phone Number
Solved
Medium
Topics
Companies
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.
Example 1:
Input: digits = “23”
Output: [“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
Example 2:
Input: digits = “”
Output: []
Example 3:
Input: digits = “2”
Output: [“a”,”b”,”c”]
Constraints:
0 <= digits.length <= 4 digits[i] is a digit in the range ['2', '9'].
https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
letter_map = {
“2”: “abc”,
“3”: “def”,
“4”: “ghi”,
“5”: “jkl”,
“6”: “mno”,
“7”: “pqrs”,
“8”: “tuv”,
“9”: “wxyz”
}
output = []
def build(i, comb):
if i == len(digits):
output.append(comb[:])
return
for c in letter_map[digits[i]]:
build(i+1, comb+c)
build(0, “”)
return output
- N-Queens
Solved
Hard
Topics
Companies
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.
Example 1:
Input: n = 4
Output: [[“.Q..”,”…Q”,”Q…”,”..Q.”],[”..Q.”,”Q…”,”…Q”,”.Q..”]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:
Input: n = 1
Output: [[“Q”]]
Constraints:
1 <= n <= 9
https://leetcode.com/problems/n-queens/description/
Trick to know if pos or neg diagonals are occupied
## neg Diag goes from top left to bottom right, in this case along the diag r-c is equal
## Pos diag goes from bottom left to top right in this case along the diag r+c is equal
## For each queen, place it at every colum in the given row to see if its valid position,
## if it is, then call backtrack to pass it on to the next queen and row (each queen will have it's own row)
from collections import defaultdict
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
b = [["." for i in range(n)] for j in range(n)]
occupied_row = set()
occupied_col = set()
occupied_lr = set() # r-c
occupied_rl = set() # r+c
movements = [[0,1], [1,0], [-1,0], [0, -1]]
res = []
def isValid(r,c):
if (r in occupied_row or c in occupied_col or r-c in occupied_lr or r+c in occupied_rl):
return False
return True
def dfs(row, queens, board):
if row == n:
res.append(["".join(row) for row in board])
return
for col in range(n):
if (row in range(n) and col in range(n) and isValid(row, col)):
occupied_row.add(row)
occupied_col.add(col)
occupied_lr.add(row-col)
occupied_rl.add(row+col)
board[row][col] = "Q"
dfs(row+1, queens, board[:])
occupied_row.remove(row)
occupied_col.remove(col)
occupied_lr.remove(row-col)
occupied_rl.remove(row+col)
board[row][col] = "."
return
dfs(0, 0, b[:])
return res- Stickers to Spell Word
Solved
Hard
Topics
Companies
Hint
We are given n different types of stickers. Each sticker has a lowercase English word on it.
You would like to spell out the given string target by cutting individual letters from your collection of stickers and rearranging them. You can use each sticker more than once if you want, and you have infinite quantities of each sticker.
Return the minimum number of stickers that you need to spell out target. If the task is impossible, return -1.
Note: In all test cases, all words were chosen randomly from the 1000 most common US English words, and target was chosen as a concatenation of two random words.
Example 1:
Input: stickers = [“with”,”example”,”science”], target = “thehat”
Output: 3
Explanation:
We can use 2 “with” stickers, and 1 “example” sticker.
After cutting and rearrange the letters of those stickers, we can form the target “thehat”.
Also, this is the minimum number of stickers necessary to form the target string.
Example 2:
Input: stickers = [“notice”,”possible”], target = “basicbasic”
Output: -1
Explanation:
We cannot form the target “basicbasic” from cutting letters from the given stickers.
Constraints:
n == stickers.length 1 <= n <= 50 1 <= stickers[i].length <= 10 1 <= target.length <= 15 stickers[i] and target consist of lowercase English letters.
Start with brute force and optimize, this can take all 30-40 mins
https://leetcode.com/problems/stickers-to-spell-word/description/
from collections import Counter
from functools import cache
class Solution:
def minStickers(self, stickers: List[str], target: str) -> int:
wordCounter = [Counter(s) for s in stickers]
# n = len(target)
# m = avg. len(sticker)
# M = num of stickers
# Time complexity (worst): M^n * m*n
# Time complexity (avg): 2^n * m*n
# Space: 2^n
def apply_sticker(sticker, state):
for c in sticker:
# clear out used letters up to how many letters are available in sticker.
state = state.replace(c, '', sticker[c])
return state
# since it is possible similar states can occur after applying different stickers, we cache the state response.
@cache
def dfs(state):
if not state:
return 0
# If we can't apply any sticker, we will return this infinity to signal, impossible.
result = float('inf')
# (s)
for sticker in wordCounter:
if state[0] in sticker:
# this is to prevent infinite loop where we apply a sticker that can't remove
# letter and call the dfs with same state. it's eq. to
# if sticker did not remove any letter afer applying, we continue to the next one.
# but with this check we do not need to apply the sticker saving mxn time because
# at some point there will be a state where it's 0 letter "Might" be in the current sticker
# hence we will eventually reach a state where we can apply this sticker.
s = apply_sticker(sticker, state)
# we can now call the method again for remaining states, since we used the sticker
# for each sticker we see if it's best option to apply it. 1 is for using 1 sticker.
# result will be updated. If none of the stickers can be used for this state, we return inf.
result = min(result, 1 + dfs(s))
return result
res = dfs(target)
return res if res < float('inf') else -1- Robot Room Cleaner
Solved
Hard
Companies: Facebook, Google 2024
You are controlling a robot that is located somewhere in a room. The room is modeled as an m x n binary grid where 0 represents a wall and 1 represents an empty slot.
The robot starts at an unknown location in the room that is guaranteed to be empty, and you do not have access to the grid, but you can move the robot using the given API Robot.
You are tasked to use the robot to clean the entire room (i.e., clean every empty cell in the room). The robot with the four given APIs can move forward, turn left, or turn right. Each turn is 90 degrees.
When the robot tries to move into a wall cell, its bumper sensor detects the obstacle, and it stays on the current cell.
Design an algorithm to clean the entire room using the following APIs:
interface Robot {
// returns true if next cell is open and robot moves into the cell.
// returns false if next cell is obstacle and robot stays on the current cell.
boolean move();
// Robot will stay on the same cell after calling turnLeft/turnRight.
// Each turn will be 90 degrees.
void turnLeft();
void turnRight();
// Clean the current cell.
void clean();
}
Note that the initial direction of the robot will be facing up. You can assume all four edges of the grid are all surrounded by a wall.
Custom testing:
The input is only given to initialize the room and the robot’s position internally. You must solve this problem “blindfolded”. In other words, you must control the robot using only the four mentioned APIs without knowing the room layout and the initial robot’s position.
Example 1:
Input: room = [[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,1,1,1,1,1,1],[0,0,0,1,0,0,0,0],[1,1,1,1,1,1,1,1]], row = 1, col = 3
Output: Robot cleaned all rooms.
Explanation: All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.
Example 2:
Input: room = [[1]], row = 0, col = 0
Output: Robot cleaned all rooms.
Constraints:
m == room.length
n == room[i].length
1 <= m <= 100
1 <= n <= 200
room[i][j] is either 0 or 1.
0 <= row < m
0 <= col < n
room[row][col] == 1
All the empty cells can be visited from the starting position.
How will you backtrack robot? (i.e move back afrer exploring each cell)
https://leetcode.com/problems/robot-room-cleaner/description/
# """
# This is the robot's control interface.
# You should not implement it, or speculate about its implementation
# """
#class Robot(object):
# def move(self):
# """
# Returns true if the cell in front is open and robot moves into the cell.
# Returns false if the cell in front is blocked and robot stays in the current cell.
# :rtype bool
# """
#
# def turnLeft(self):
# """
# Robot will stay in the same cell after calling turnLeft/turnRight.
# Each turn will be 90 degrees.
# :rtype void
# """
#
# def turnRight(self):
# """
# Robot will stay in the same cell after calling turnLeft/turnRight.
# Each turn will be 90 degrees.
# :rtype void
# """
#
# def clean(self):
# """
# Clean the current cell.
# :rtype void
# """
from operator import add
class Solution(object):
def cleanRoom(self, robot):
"""
:type robot: Robot
:rtype: None
"""
# Doing it via DFS
def reverse(r):
# face back move and face in same direction as started
r.turnLeft()
r.turnLeft()
r.move()
r.turnRight()
r.turnRight()
direction_movement = {'right': (0, 1), 'left' : (0, -1), 'up': (-1, 0), 'down': (1,0)}
direction_cycle = {'up': 'right', 'right': 'down', 'down': 'left', 'left': 'up'}
visited = set()
next_loc = lambda a,b: tuple(map(add, a, b))
def dfs(r, loc, direction):
# Clean when you reach the new cell
r.clean()
visited.add(loc)
# Continue where facing, if can't turn right till you can find valid movement
# after 4 turns face the same direction as started and then move back to prev position (backtrack)
for _ in range(4):
movement = direction_movement[direction]
new_loc = next_loc(movement, loc)
if new_loc not in visited and r.move():
dfs(r, new_loc, direction)
r.turnRight()
direction = direction_cycle[direction]
# explored all paths move back
reverse(r)
dfs(robot, (0,0), 'up')- Palindrome Partitioning II
Hard
Given a string s, partition s such that every substring of the partition is a
palindrome
.Return the minimum cuts needed for a palindrome partitioning of s.
Example 1:
Input: s = “aab”
Output: 1
Explanation: The palindrome partitioning [“aa”,”b”] could be produced using 1 cut.
Example 2:
Input: s = “a”
Output: 0
Example 3:
Input: s = “ab”
Output: 1
Constraints:
1 <= s.length <= 2000
s consists of lowercase English letters only.
15 minutes
https://leetcode.com/problems/palindrome-partitioning-ii/
from functools import cache
class Solution:
def minCut(self, s: str) -> int:
def isPalin(s):
return s[::-1] == s
@cache
def backtrack(i):
if i == len(s):
return -1
elif isPalin(s[i:]):
return 0
cuts = float('inf')
for idx in range(i+1, len(s)+1):
if isPalin(s[i:idx]):
cuts = min(cuts, 1+backtrack(idx))
return cuts
return backtrack(0)
You can use Dynamic programming to check isPalin to make it faster but not needed to pass.
O(n^2), O(n)
- Remove Invalid Parentheses
Hard
Companies: Facebook 2024
Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.
Return a list of unique strings that are valid with the minimum number of removals. You may return the answer in any order.
Example 1:
Input: s = “()())()”
Output: [”(())()”,”()()()”]
Example 2:
Input: s = “(a)())()”
Output: [“(a())()”,”(a)()()”]
Example 3:
Input: s = “)(“
Output: [””]
Constraints:
1 <= s.length <= 25
s consists of lowercase English letters and parentheses ‘(‘ and ‘)’.
There will be at most 20 parentheses in s.
https://leetcode.com/problems/remove-invalid-parentheses/
Create Suffix sum and then identify pressing conditions. Presssing conditions are those where you have to take one or the other step. ie. add or skip the parenthesis. Any other condition besides pressing condition, you can be ambivalent. i.e Choose to add or not i.e call recursion twice.
Once you reach the end, just append your solution and pop the previous ones if they are smaller than the one you have.
Worst case for every letter we have two choices.
O(2^n)
Space complexity:
We need to build the prefix array. O(n)
from itertools import accumulate
from collections import defaultdict
from functools import cache
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
mappings = defaultdict(lambda: [0,0])
mappings['('] = [1,0]
mappings[')'] = [0,1]
suffix_counts = list(accumulate(map(lambda c: mappings[c], s[::-1]), lambda a,b: [i+j for i,j in zip(a,b)]))[::-1]
min_removals = 26
output = []
@cache
def dfs(p, p_open, p_close, skipped, idx):
nonlocal min_removals
if idx == len(s):
if p_open == p_close and skipped <= min_removals:
min_removals = skipped
while output and len(output[-1]) < len(p):
output.pop()
output.append(p)
return
future_open, future_close = suffix_counts[idx]
excess_open = (p_open-p_close)
if s[idx] == '(':
if excess_open + future_open <= future_close:
# If excess open and future open are less than close available in future, we have to add this one.
dfs(p+'(', p_open+1, p_close, skipped, idx+1)
elif excess_open >= future_close:
# if excess opens are already in excess of what we can find to balance in future, we need to skip this.
dfs(p, p_open, p_close, skipped+1, idx+1)
else:
# other than the two cases above, we can chose to add or not this as there is no pressing condition.
dfs(p+'(', p_open+1, p_close, skipped, idx+1)
dfs(p, p_open, p_close, skipped+1, idx+1)
elif s[idx] == ')':
# We have to skip this if we have p_close >= p_open or we can skip if there is enough close in future to cover excess open
if p_close >= p_open or excess_open < future_close:
dfs(p, p_open, p_close, skipped+1, idx+1)
if p_close < p_open:
# If more open than closed or future close excess is > p_open we can add it
dfs(p+')', p_open, p_close+1, skipped, idx+1)
else:
dfs(p+s[idx], p_open, p_close, skipped, idx+1)
dfs('', 0,0,0,0)
return output
https://leetcode.com/problems/remove-invalid-parentheses/solutions/5523318/using-suffix-sum-cache-insanely-fast-and-easy-to-understand/
- Verbal Arithmetic Puzzle
Hard
Companies: Atlassian
Given an equation, represented by words on the left side and the result on the right side.
You need to check if the equation is solvable under the following rules:
Each character is decoded as one digit (0 - 9).
No two characters can map to the same digit.
Each words[i] and result are decoded as one number without leading zeros.
Sum of numbers on the left side (words) will equal to the number on the right side (result).
Return true if the equation is solvable, otherwise return false.
Example 1:
Input: words = [“SEND”,”MORE”], result = “MONEY”
Output: true
Explanation: Map ‘S’-> 9, ‘E’->5, ‘N’->6, ‘D’->7, ‘M’->1, ‘O’->0, ‘R’->8, ‘Y’->’2’
Such that: “SEND” + “MORE” = “MONEY” , 9567 + 1085 = 10652
Example 2:
Input: words = [“SIX”,”SEVEN”,”SEVEN”], result = “TWENTY”
Output: true
Explanation: Map ‘S’-> 6, ‘I’->5, ‘X’->0, ‘E’->8, ‘V’->7, ‘N’->2, ‘T’->1, ‘W’->’3’, ‘Y’->4
Such that: “SIX” + “SEVEN” + “SEVEN” = “TWENTY” , 650 + 68782 + 68782 = 138214
Example 3:
Input: words = [“LEET”,”CODE”], result = “POINT”
Output: false
Explanation: There is no possible mapping to satisfy the equation, so we return false.
Note that two different characters cannot map to the same digit.
Constraints:
2 <= words.length <= 5
1 <= words[i].length, result.length <= 7
words[i], result contain only uppercase English letters.
The number of different characters used in the expression is at most 10.
Hint: Reverse strings
Just go brute force backtracking
Solution From: https://leetcode.com/problems/verbal-arithmetic-puzzle/solutions/2912760/similar-to-ye15-solution-with-more-comments-for-easier-understanding
Modified to add optimizations (Reverse sort and combining some if else) these improve performance significantly. 450ms -> 320ms (more than 20% improvement)
from functools import reduce
class Solution:
def isSolvable(self, words: List[str], result: str) -> bool:
max_len = reduce(lambda ml, w: max(ml, len(w)), words, 0)
if max_len > len(result):
return False
words = list(map(lambda x: x[::-1], words))
# Since words are reverse sorted based on length, as soon as we hit a word where the column
# is longer than the length, we know no other word downstream will have longer length.
# abcde
# bcde
# cde
# de
# Once we hit c_idx 3, on w_idx 2, we know we should just move to next column from first word..
words = sorted(words, key=lambda x: len(x), reverse=True)
words = [result[::-1]] + words
max_len = max(max_len, len(result))
mapping = {}
state = [False] * 10
def backtracking(w_idx, c_idx, total):
if c_idx == max_len:
# we went through all columns at this point total should be zero
return total == 0
if w_idx == len(words) or c_idx >= len(words[w_idx]):
# Reached end of all words for given c_idx, the total is either 0 or multiple of 10
# which signifies that after subtracting the result's c_idx letter the result was valid.
# eg. 7 + 6 - 3 = 10 which means if we added 7 + 6 and the result was 3 it would be valid as the
# 1 would become carry for next set of integers.
return total % 10 == 0 and backtracking(0, c_idx+1, total // 10)
if words[w_idx][c_idx] in mapping:
digit = mapping[words[w_idx][c_idx]]
# Digit is zero and we are at the first letter, can't be possible unless only one len
if digit == 0 and (c_idx == (len(words[w_idx]) - 1) and len(words[w_idx]) > 1):
return False
if w_idx == 0:
return backtracking(w_idx + 1, c_idx, total - digit)
else:
return backtracking(w_idx + 1, c_idx, total + digit)
else:
# We do reversed here because we start with the first word being the result word, we should assign it
# higher value than the others since its the result of sum of the rest. This improves performance
for digit, used in reversed(list(enumerate(state))):
# digit is unused, if it is eq. to zero it can not be applied as the first
if not used and (digit != 0 or 0 == c_idx or len(words[w_idx]) == 1 or c_idx < (len(words[w_idx]) - 1)):
state[digit] = True
mapping[words[w_idx][c_idx]] = digit
# we are at the last word (i.e the result word, now we subtract it's value)
if w_idx == 0 and backtracking(w_idx + 1, c_idx, total - digit):
return True
elif w_idx > 0 and backtracking(w_idx + 1, c_idx, total + digit):
return True
state[digit] = False
mapping.pop(words[w_idx][c_idx])
return backtracking(0,0,0)
