Skills for tackling LeetCode problems - BFS for Subsets.
BFS is efficient to deal with permutations and combinations of a given set of elements.
1. Subsets
Given a set with distinct elements, find all of its distinct subsets.
- For each number in the list, add it to each of the sets.
- Append the new sets to the previous sets.
# Time complexity O(N*2^N). In each step, the number of subsets doubles as we add each element to all the existing subsets. This takes O(2^N).
# Space complexity O(N*2^N). We will have O(2^N) subsets and each subset can take up to O(N) space.
def find_subsets(nums):
subsets = []
subsets.append([])
for num in nums:
n = len(subsets)
for i in range(n):
set1 = list(subsets[i])
set1.append(num)
subsets.append(set1)
return subsets
2. Subsets with Duplicates
Given a set of numbers that might contain duplicates, find all of its distinct subsets.
- sort to ensure duplicates are near to each other
- for duplicates, only add to the subsets that is created in the previous step
# Time complexity O(N*2^N). Space compelxity O(N*2^N).
def find_subsets(nums):
nums.sort()
subsets = []
subsets.append([])
start, end = 0, 0
for i in range(len(nums)):
start = 0
if i > 0 and nums[i] == nums[i-1]: # duplicates
start = end + 1 # start index becomes the first of previously added subsets
end = len(subsets) - 1 # end index of the previous subsets
for j in range(start, end + 1):
set1 = list(subsets[j])
set1.append(nums[i])
subsets.append(set1)
return subsets
3. Permutations
Given a set of distinct numbers find all of its permutations. (N distinct elements have N! permutations).
When we add a new number, we take each permutation of the previous step and insert the new number in every position to generate the new permutations.
# Time complexity O(N*N!). There are N! permutations. And it takes O(N) to insert a permutation.
# Space complexity O(N*N!). N! permutations and each contains N elements.
from collections import deque
def find_permutations(nums):
length = len(nums)
result = []
permutations = deque() # BFS
permutations.append([])
for num in nums:
for i in range(len(permutations)):
pre = permutations.popleft()
for j in range(len(pre) + 1):
cur = list(pre)
cur.insert(j, num) # insert num at each position
if len(cur) == length: # if the new permutation is full
result.append(cur)
else: # append to queue
permutations.append(cur)
return result
4. String Permutation by Changing Case
Given a string, find all of its permutations preserving the character sequence but changing case.
# Time complexity O(N*2^N). Space complexity O(N*2^N).
def find_letter_case_string_permutations(str):
permutations = []
permutations.append(str)
for i in range(len(str)):
if str[i].isalpha():
n = len(permutations)
for j in range(n):
letter = list(permutations[j])
letter[i] = letter[i].swapcase()
permutations.append(''.join(letter))
return permutations
5. Balanced Parenthesis
For a given number N, write a function to generate all combination of N pairs of balanced parentheses.
# Time complexity O(N*2^N). Space complexity O(N*2^N).
from collections import deque
class ParenthesesString:
def __init__(self, str, openCount, closeCount):
self.str = str
self.openCount = openCount
self.closeCount = closeCount
def generate_valid_parentheses(num):
result = []
queue = deque()
queue.append(ParenthesesString("", 0, 0))
while queue:
ps = queue.popleft()
if ps.openCount == num and ps.closeCount == num:
result.append(ps.str)
else:
if ps.openCount < num:
queue.append(ParenthesesString(ps.str + "(", ps.openCount + 1, ps.closeCount))
if ps.openCount > ps.closeCount:
queue.append(ParenthesesString(ps.str + ")", ps.openCount, ps.closeCount + 1))
return result
6. Unique Generalized Abbreviations
Given a word, write a function to generate all of its unique generalized abbreviations. A generalized abbreviation of a word can be generated by replacing each substring of the word with the count of characters in the substring. Take the example of ‘ab’ which has four substrings: ‘’, ‘a’, ‘b’, ‘ab’. After replacing these substrings in the actual word by the count of characters, we get all the generalized abbreviations: ‘ab’, ‘1b’, ‘a1’, and ‘2’.
# Time complexity O(N*2^N). Space complexity O(N*2^N).
from collections import deque
class AbbreviatedWord:
def __init__(self, str, start, count):
self.str = str
self.start = start
self.count = count
def generate_generalized_abbreviation(word):
length = len(word)
result = []
queue = deque()
queue.append(AbbreviatedWord(list(),0,0))
while queue:
cur = queue.popleft()
if cur.start == length: # if the string is in full length
if cur.count != 0: # it need a number for the fully abbreviated string
cur.str.append(str(cur.count))
result.append(''.join(cur.str))
else:
# continue abbreviating by incrementing the count
queue.append(AbbreviatedWord(list(cur.str), cur.start + 1, cur.count + 1))
if cur.count != 0: # it need a number to abbreviate
cur.str.append(str(cur.count))
# do not abbreviate
new = list(cur.str)
new.append(word[cur.start])
queue.append(AbbreviatedWord(new, cur.start + 1, 0))
return result
Recursive solution:
# pass 'cur' and 'word' through recursive function
def generate_generalized_abbreviation(word):
result = []
recursive(word, list(), 0, 0, result)
return result
def recursive(word, cur, start, count, result):
if start == len(word):
if count != 0:
cur.append(str(count))
result.append(''.join(cur))
else:
# abbreviate the string by adding nothing to the string but adding count
recursive(word, list(cur), start + 1, count + 1, result)
if count != 0: # if need a number to abbreviate the previous empty space
cur.append(str(count))
# do not abbreviate
new = list(cur)
new.append(word[start])
recursive(word, new, start + 1, 0, result)
