We use this topic to discuss the backtracking algorithm, which is a recursive algorithm that traverses a tree depth-first (because it traverses the whole tree, the time complexity is generally not low).

The difference between the backtracking algorithm and the DFS algorithm is that the backtracking algorithm will judge

]]>We use this topic to discuss the backtracking algorithm, which is a recursive algorithm that traverses a tree depth-first (because it traverses the whole tree, the time complexity is generally not low).

The difference between the backtracking algorithm and the DFS algorithm is that the backtracking algorithm will judge each node in the process of traversal. If it does not meet the conditions, it will backtrack to the previous node and then traverse it. Let's take the simplest example to distinguish when to use the backtracking algorithm and when to use the DFS algorithm.

For example, we have an array, each element in the array is a choice, and we need to choose an element that meets the condition from these choices. Then we can use the backtracking algorithm, because in the process of traversing, we can judge each element, if it does not meet the conditions, we will backtrack to the previous element, and then traverse.

But if we want to select all the eligible elements from these choices, then we need to use the DFS algorithm, because we need to traverse the whole tree and find all the eligible elements.

The idea of the backtracking algorithm is very simple and can be roughly divided into the following steps:

- Path: make a choice
- Select: Make a selection from the selection list
- Condition: If the end condition is met, the selection is added to the result.
- Undo: Undo the selection

The pseudocode is as follows:

```
result = []
def backtrack(path, selectionList):
if meet the end condition:
result.add(path)
return
for selection in selectionList:
make a choice
backtrack(path, selectionList)
undo the choice
```

The description of this problem is to give a string containing only the numbers 2-9 and return all the letter combinations it can represent. Answers can be returned in any order. The mapping of numbers to letters is given as follows (same as phone keys). Note that 1 does not correspond to any letter.

test cases:

```
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Input: digits = ""
Output: []
```

The idea of this problem is the idea of backtracking algorithm. We can put the letters corresponding to each number into an array, and then backtrack the array, and finally get all the results. Specifically, every phone number can be seen as a tree, for example, 2 can be seen as such a tree, and the corresponding branch is the letter corresponding to 2. Then we can backtrack the tree and get all the results.

```
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
# use a dictionary to store the letters corresponding to each number
dic = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
}
res = []
def backtrack(index, path):
if index == len(digits): # if the index is equal to the length of the input, it means that the result has been traversed
res.append("".join(path))
return
possible = dic[digits[index]]
for letter in possible:
path.append(letter) # make a choice
backtrack(index + 1, path) # enter the next level
path.pop() # undo the choice
backtrack(0, [])
return res
```

Complexity analysis:

- Time complexity: O (3 ^ _ 4 ^ n), where m is the number of digits corresponding to 3 letters in the input (including digits 2, 3, 4, 5, 6 and 8), n is the number of digits corresponding to 4 letters in the input (including digits 7 and 9), and m + n is the total number of input digits. When the input contains m numbers corresponding to 3 letters and n numbers corresponding to 4 letters, the total number of different letter combinations is 3 ^ m _ m 4 ^ n), each letter combination needs to be traversed.
- Space complexity: O (m + n), where m is the number of digits corresponding to 3 letters in the input, n is the number of digits corresponding to 4 letters in the input, and m + n is the total number of input digits. In addition to the return value, the space complexity mainly depends on the hash table and the number of recursive calls in the backtracking process. The size of the hash table is independent of the input and can be regarded as a constant. The maximum number of recursive calls is m + n.

Given an array of candidates with no repeating elements and a target number target, the description of this problem is to find all the combinations in candidates that can make the sum of numbers target. Numbers in candidates can be selected repeatedly without restriction.

test cases:

```
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
```

The idea of this problem is also the idea of backtracking algorithm. We can regard every number as a tree. For example, when candidates = [2, 3, 6, 7] and target = 7, we can regard it as such a tree:

```
2
/ | \
2 3 6
/ \ / \ / \
2 3 2 3 2 3
```

Then we can backtrack the tree and get all the results.

```
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
def backtrack(index, path, rest):
if rest == 0: # if the target is 0, it means that the result has been traversed
res.append(path[:])
return
if rest < 0: # if the target is less than 0, it means that the result is not feasible
return
for i in range(index, len(candidates)):
path.append(candidates[i]) # make a choice
backtrack(i, path, rest - candidates[i]) # enter the next level
path.pop() # undo the choice
backtrack(0, [], target)
return res
```

Complexity analysis:

- Time complexity: O (S), where S is the sum of the lengths of all feasible solutions. In the worst case, all combinations are feasible, for example, candidates = [1, 1, 1, 1,1,1,1,1, 1,1,1,1], target = 11. In this case, there are O (2 ^ N) combinations, and each combination is O (N) long, so the time complexity is O (N \ * 2 ^ N). In the best case, the number in the combination is 1, and the time complexity is O (N).
- Space complexity: O (target). In addition to the answer array, the space complexity depends on the stack depth of the recursion, which, in the worst case, requires O (target) layers of recursion.

Given an array candidates and a target number target, the description of this problem is to find all the combinations in candidates that can make the sum of numbers target. Each number in candidates can be used only once in each combination.

test cases:

```
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
Input: candidates = [2,5,2,1,2], target = 5
Output: [[1,2,2],[5]]
```

The difference between this question and the previous one is that the numbers in the array in the previous question can be selected repeatedly without restriction, while the numbers in the array in this question can only be used once in each combination. Then we can make some changes to this problem, for example, when recursing, we can add one to the index, so that we can ensure that each number will only be used once.

```
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
def backtrack(start, path, rest):
if rest == 0: # if the target is 0, it means that the result has been traversed
res.append(path[:])
return
if rest < 0: # if the target is less than 0, it means that the result is not feasible
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i - 1]:
# if the current number is equal to the previous number, it means that it has been traversed, so return directly
# For example, candidates = [1,1,2,5,6,7,10], target = 8
# When i = 1, path = [1], rest = 7, at this time i > start and candidates[i] == candidates[i - 1]
# So skip directly without recursion
continue
path.append(candidates[i]) # make a choice
backtrack(i + 1, path, rest - candidates[i]) # enter the next level
path.pop() # undo the choice
candidates.sort() # sort the array
backtrack(0, [], target)
return res
```

Complexity analysis:

- Time complexity: O (S), where S is the sum of the lengths of all feasible solutions. In the worst case, all combinations are feasible, for example, candidates = [1, 1, 1, 1,1,1,1,1, 1,1,1,1], target = 11. In this case, there are O (2 ^ N) combinations, and each combination is O (N) long, so the time complexity is O (N \ * 2 ^ N). In the best case, the number in the combination is 1, and the time complexity is O (N).
- Space complexity: O (target). In addition to the answer array, the space complexity depends on the stack depth of the recursion, which, in the worst case, requires O (target) layers of recursion.

The description of this problem is to give an integer K and an integer n, and find all the combinations of the number of K whose sum is n. Only positive integers from 1 to 9 are allowed in the combination, and there are no duplicate numbers in each combination.

test cases:

```
Input: k = 3, n = 7
Output: [[1,2,4]]
Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Input: k = 4, n = 1
Output: []
Input: k = 3, n = 2
Output: []
Input: k = 9, n = 45
Output: [[1,2,3,4,5,6,7,8,9]]
```

The difference between this question and the previous one is that the numbers in the array in the previous question can be selected repeatedly without restriction, while the numbers in the array in this question can only be used once in each combination. Then we can make some changes to this problem, for example, when recursing, we can add one to the index, so that we can ensure that each number will only be used once.

```
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res = []
def backtrack(start, path, rest):
if rest == 0 and len(path) == k: # if the target is 0 and the length of the path is k, it means that the result has been traversed
res.append(path[:])
return
if rest < 0 or len(path) >= k: # if the target is less than 0 or the length of the path is greater than or equal to k, it means that the result is not feasible
return
for i in range(start, 10):
path.append(i) # make a choice
backtrack(i + 1, path, rest - i) # enter the next level
path.pop() # undo the choice
backtrack(1, [], n)
return res
```

Complexity analysis:

- Time complexity: O (9!), where 9! = 362880。
- Space complexity: O (K), where K is the length of the combination.

The description of this problem is that given an array nums containing no repeated numbers, all possible permutations of these numbers are returned. You can return the answers in any order.

test cases:

```
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Input: nums = [1]
Output: [[1]]
```

The idea of this problem is also the idea of backtracking algorithm. We can regard every number as a tree. For example, when nums = [1,2,3], we can regard it as such a tree:

```
1
/ | \
2 3 2
/ \ / \ / \
3 2 2 1 1 3
```

Then we can backtrack the tree and get all the results.

```
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
def backtrack(path):
if len(path) == len(nums): # if the length of the path is equal to the length of the array, it means that the result has been traversed
res.append(path[:])
return
for num in nums:
if num in path: # if the number is already in the path, it means that it has been traversed, so skip directly
continue
path.append(num) # make a choice
backtrack(path) # enter the next level
path.pop() # undo the choice
backtrack([])
return res
```

In fact, this problem can also be solved using python packages, such as the permutations function in itertools, which can return all combinations of an array, such as:

```
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
return list(itertools.permutations(nums))
```

Complexity analysis:

- Time complexity: O (N \ * N!), where N is the length of the array.
- Space complexity: O (N \ * N!), where N is the length of the array.

test cases:

```
Input: nums = [1,1,2]
Output: [[1,1,2],[1,2,1],[2,1,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]]
```

The difference between this question and the previous one is that the numbers in the array in this question can be repeated. Then we can use counter to record the number of times each number appears, and then add or subtract the corresponding number before and after the backtracking.

```
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
results = []
def backtrack(path, counter):
if len(path) == len(nums):
# if the length of the path is equal to the length of the array, it means that the result has been traversed
results.append(path[:])
return
for num in counter:
if counter[num] > 0: # if the number of times the number appears is greater than 0, it means that it has not been traversed
path.append(num)
counter[num] -= 1 # counter minus one
backtrack(path, counter)
path.pop() # undo the choice
counter[num] += 1 # counter plus one
backtrack([], Counter(nums))
return results
```

Or we can use the visited array to record whether each number has been visited or not, so that we don't need to use counter.

```
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def backtrack(res, cur, nums, visited):
if len(cur) == len(nums):
res.append(cur[:])
for i in range(len(nums)):
if (visited[i] == 1) or (i > 0 and nums[i] == nums[i - 1] and visited[i - 1] == 0):
continue
visited[i] = 1
cur.append(nums[i])
backtrack(res, cur, nums, visited)
visited[i] = 0
cur.pop()
return res
res = []
boolean = [0 for _ in range(len(nums))]
nums.sort()
return backtrack(res, [], nums, boolean)
```

In fact, this problem can also be solved using python packages, such as the permutations function in itertools, which can return all combinations of an array, such as:

```
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
return list(set(itertools.permutations(nums)))
```

Complexity analysis:

- Time complexity: O (N \ * N!), where N is the length of the array.
- Space complexity: O (N \ * N!), where N is the length of the array.

test cases:

```
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Input: nums = [0]
Output: [[],[0]]
```

The description of this problem is to give an integer array nums without repeated elements and return all possible subsets (power sets) of the array. The solution set cannot contain duplicate subsets.

The idea of this problem is also the idea of backtracking algorithm. We can regard every number as a tree. For example, when nums = [1,2,3], we can see that the subset tree is such a tree:

```
[]
/ | \
1 2 3
/ \ / \ / \
2 3 3 1 1 2
/ \ / \ / \ / \ / \ / \
3 1 1 2 2 1 3 3 2 2 1
```

In fact, this is wrong, because there are repeated subsets in this tree, such as [1,2] and [2,1], so we need to prune the tree. The way to prune is to pass a start parameter when we recurse. This parameter represents the subscript of the current number. For example, when we traverse to 2, The start is 1, so we only need to iterate through the numbers after 2, so there are no duplicate subsets.

Then we can backtrack the tree and get all the results.

```
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
def backtrack(start, path):
res.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i]) # make a choice
backtrack(i + 1, path) # start from the next number
path.pop() # undo the choice
backtrack(0, [])
return res
```

In fact, this problem can also be solved using python packages, such as the combinations function in itertools, which can return all combinations of an array, such as:

```
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
return chain.from_iterable(chain([combinations(nums, i) for i in range(len(nums) + 1)]))
```

Complexity analysis:

- Time complexity: O (N \ * 2 ^ N), where N is the length of the array.
- Space complexity: O (N \ * 2 ^ N), where N is the length of the array.

test cases:

```
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Input: nums = [0]
Output: [[],[0]]
```

The difference between this question and the previous one is that the array of this question contains duplicate elements, so we need to prune the tree. The pruning method is to pass in a start parameter when recursing. This parameter represents the subscript of the current number. For example, when we traverse to 2, start is 1. Then we only need to go through the numbers after 2, so that there will be no duplicate subsets. And it should be noted that when we traverse, if the current number is equal to the previous number, it means that we have traversed and returned directly.

```
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = []
def backtrack(start, path):
res.append(path[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]: # if the current number is equal to the previous number, it means that we have traversed and returned directly
continue
path.append(nums[i]) # make a choice
backtrack(i + 1, path) # start from the next number
path.pop() # undo the choice
nums.sort() # sort the array
backtrack(0, [])
return res
```

In fact, this problem can also be solved using python packages, such as the combinations function in itertools, which can return all combinations of an array, such as:

```
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
return set([tuple(sorted(item)) for item in chain.from_iterable(chain([combinations(nums, i) for i in range(len(nums) + 1)]))])
```

Complexity analysis:

- Time complexity: O (N \ * 2 ^ N), where N is the length of the array.
- Space complexity: O (N \ * 2 ^ N), where N is the length of the array.

test cases:

```
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Input: n = 1
Output: ["()"]
```

The description of this problem is that given an integer n, all valid combinations consisting of n pairs of brackets are generated. A valid combination needs to satisfy: the left parenthesis must be closed in the correct order.

The idea of this problem is also the idea of backtracking algorithm. We can regard each bracket as a tree. For example, when n = 3, we can regard it as such a tree:

Then we can backtrack the tree and get all the results.

```
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
def backtrack(left, right, path):
if left == 0 and right == 0: # if the number of left and right parentheses is 0, it means that the result is obtained
res.append("".join(path))
return
if left > right: # if the number of left parentheses is greater than the number of right parentheses, it means that the result is not obtained
return
if left > 0: # if the number of left parentheses is greater than 0, you can add a left parenthesis
path.append("(")
backtrack(left - 1, right, path)
path.pop()
if right > 0: # if the number of right parentheses is greater than 0, you can add a right parenthesis
path.append(")")
backtrack(left, right - 1, path)
path.pop()
backtrack(n, n, [])
return res
```

Complexity analysis:

- Time complexity: O (4 ^ n/sqrt (n)). During backtracking, each answer takes O (n) time to copy into the answer array.
- Space complexity: O (n). In addition to the answer array, the space we need depends on the depth of the recursion stack. Each layer of recursion function needs O (1) space. At most 2 n layers of recursion, so the space complexity is O (n).

test cases:

```
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
```

The description of this problem is given a two-dimensional grid and a word, find out whether the word exists in the grid. Words must be formed alphabetically by letters in adjacent cells, where "adjacent" cells are those that are horizontally or vertically adjacent. Letters in the same cell are not allowed to be reused.

The idea of this problem is also the idea of backtracking algorithm. We can regard each letter as a tree, such as board = [ [ "A", "B", "C", "E"], [ "S", 'F', 'C', 'S'], [ "A",'D ','E', E ']]. When word = "ABCCED", we can see such a tree:

```
A
/ | \
B S D
/ \ / \ / \
C D F E E C
/ \ / \ / \ / \ / \ / \
C E C C C S E E C C
```

Then we can backtrack the tree and get all the results.

```
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def backtrack(i, j, index):
if index == len(word): # if the index is equal to the length of the word, it means that the result is obtained
return True
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[index]:
# if the index is out of bounds or the current letter is not equal to the letter in the word, it means that the result is not obtained
return False
board[i][j] = "#" # make the current letter invalid
res = backtrack(i + 1, j, index + 1) or backtrack(i - 1, j, index + 1) or backtrack(i, j + 1, index + 1) or backtrack(i, j - 1, index + 1) # backtracking
board[i][j] = word[index] # restore the current letter
return res
for i in range(len(board)):
for j in range(len(board[0])):
if backtrack(i, j, 0):
return True
return False
```

Complexity analysis:

- Time complexity: O (M \ _ N \ _ 4 ^ L), where M and N are the height and width of the two-dimensional grid, respectively, and L is the length of the string word. Every time the function backtrack is called, except for the first time we can enter four branches, the rest of the time we will enter up to three branches (because each position can only be used once, so the branches that come through can not go back). Since the word length is L, the time complexity of the backtracking function is O (3 ^ L). And we want to perform O (M \ _ N) times, so the total time complexity is O (M \ _ N \ * 3 ^ L).
- Space complexity: O (L), where L is the length of the string word. Stack space for mostly recursive calls.

test cases:

```
Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]
Input: s = "0000"
Output: ["0.0.0.0"]
Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
```

The description of this problem is to give a string s containing only numbers and return all the valid IP addresses that can be obtained from s. You can return the answers in any order.

The idea of this problem is also the idea of backtracking algorithm, we can regard every number as a tree, for example, when s = "25525511135", we can regard it as such a tree:

```
2
/ | \
5 5 5
/ \ / \ / \
5 5 5 5 5 5
/ \ / \ / \ / \ / \ / \
2 5 2 5 2 5 2 5 2 5
```

Then we can backtrack the tree and get all the results.

```
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
res = []
def backtrack(start, path):
if start == len(s) and len(path) == 4:
# if the start index is equal to the length of the string s and the length of the path is equal to 4, it means that the result is obtained
res.append(".".join(path))
return
if len(path) > 4: # if the length of the path is greater than 4, it means that the result is not obtained
return
for i in range(start, len(s)):
if s[start] == "0" and i > start:
# if the first letter of the current number is 0 and the length of the current number is greater than 1, it means that the result is not obtained
return
num = int(s[start:i + 1])
if num > 255: # if the current number is greater than 255, it means that the result is not obtained
return
path.append(str(num)) # make the current number valid
backtrack(i + 1, path) # backtracking
path.pop() # restore the current number
backtrack(0, [])
return res
```

Complexity analysis:

- Time complexity: O (1), because the length of the IP address is fixed.
- Space complexity: O (1), because the length of the IP address is fixed.

test cases:

```
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Input: s = "a"
Output: [["a"]]
```

The description of this problem is that given a string s, divide s into some substrings, so that each substring is a palindrome string. Returns s all possible partitioning schemes.

The idea of this problem is also the idea of backtracking algorithm. We can regard every letter as a tree. For example, when s = "AAB", we can regard it as such a tree:

```
a
/ | \
a a b
/ \ / \ / \
a b a b a b
/ \ / \ / \ / \ / \ / \
b a b a b a b a b a
```

Then we can backtrack the tree and get all the results.

```
class Solution:
def partition(self, s: str) -> List[List[str]]:
res = []
def backtrack(index, path):
if index == len(s): # if the index is equal to the length of the string s, it means that the result is obtained
res.append(path[:])
return
for i in range(index, len(s)):
if self.isPalindrome(s[index:i + 1]): # if the current string is a palindrome string
path.append(s[index:i + 1]) # make the current string valid
backtrack(i + 1, path) # backtracking
path.pop() # restore the current string
backtrack(0, [])
return res
def isPalindrome(self, s: str) -> bool:
return s == s[::-1]
```

Complexity analysis:

- Time complexity: O (N \ * 2 ^ N), where N is the length of the string.
- Space complexity: O (N \ * 2 ^ N), where N is the length of the string.

test cases:

```
Input: n = 1
Output: []
Input: n = 37
Output: []
Input: n = 12
Output: [[2,6],[2,2,3],[3,4]]
Input: n = 32
Output: [[2,16],[2,2,8],[2,2,2,4],[2,2,2,2,2],[2,4,4],[4,8]]
```

The description of this problem is to give an integer n and return all possible combinations of the factors of n. A factor is a number that is divisible by another number.

The idea of this problem is also the idea of backtracking algorithm. We can regard every number as a tree. For example, when n = 12, we can regard it as such a tree:

```
12
/ | \
2 3 4
/ \ / \ / \
2 6 3 4 4 3
/ \ / \ / \ / \ / \ / \
3 4 2 3 2 2 3 2 2 2
```

Then we can backtrack the tree and get all the results.

```
class Solution:
def getFactors(self, n: int) -> List[List[int]]:
res = []
def backtrack(index, path, target):
if target == 1 and len(path) > 1: # if the target is equal to 1 and the length of the path is greater than 1, it means that the result is obtained
res.append(path[:])
return
for i in range(index, target + 1):
if target % i == 0: # if the current number is a factor of the target
path.append(i) # make the current number valid
backtrack(i, path, target // i) # backtracking
path.pop() # restore the current number
backtrack(2, [], n)
return res
```

Complexity analysis:

- Time complexity: O (N \ * log N), where N is the size of the integer n.
- Space complexity: O (N \ * log N), where N is the size of the integer n.

test cases:

```
Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]
Input: turnedOn = 9
Output: []
```

The description of this problem is given a non-negative integer turnedOn, which represents the number of LEDs currently on, and returns all possible times. You can return the answers in any order.

The idea of this problem is also the idea of backtracking algorithm. We can regard every number as a tree. For example, when turnedOn = 1, we can regard it as such a tree:

```
0
/ | \
1 2 4
/ \ / \ / \
2 4 3 5 5 6
/ \ / \ / \ / \ / \ / \
3 5 4 6 5 7 6 8 7 9
```

Then we can backtrack the tree and get all the results.

```
class Solution:
def readBinaryWatch(self, turnedOn: int) -> List[str]:
res = []
def backtrack(index, path, hour, minute):
if hour > 11 or minute > 59:
return
if turnedOn == 0:
res.append(str(hour) + ":" + "0" * (minute < 10) + str(minute))
return
for i in range(index, 10):
if i < 4:
backtrack(i + 1, path, hour + (1 << i), minute)
else:
backtrack(i + 1, path, hour, minute + (1 << (i - 4)))
backtrack(0, [], 0, 0)
return res
```

Complexity analysis:

- Time complexity: O (1).
- Space complexity: O (1).

test cases:

```
Input: n = 2
Output: 2
Input: n = 1
Output: 1
```

The description of this problem is to give a positive integer n and return all possible beautiful permutations of n numbers. An array is considered to be a beautiful permutation if its ith element is divisible by I.

The idea of this problem is also the idea of backtracking algorithm. We can regard every number as a tree. For example, when n = 2, we can regard it as such a tree:

```
1
/ | \
2 1 2
```

Then we can backtrack the tree and get all the results.

```
class Solution:
def countArrangement(self, n: int) -> int:
res = []
def backtrack(index, path):
if index == n + 1:
res.append(path[:])
return
for i in range(1, n + 1):
if i in path:
continue
if i % index == 0 or index % i == 0:
path.append(i)
backtrack(index + 1, path)
path.pop()
backtrack(1, [])
return len(res)
```

Complexity analysis:

- Time complexity: O (K), where K is the number of eligible permutations.
- Space complexity: O (n), where n is the size of a positive integer n.

test cases:

```
Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]
Input: s = "3z4"
Output: ["3z4","3Z4"]
```

The description of this problem is to give a string s and return all possible upper and lower case letters. Letters are case-sensitive.

The idea of this problem is also the idea of backtracking algorithm. We can regard every letter as a tree. For example, when s = "a1b2", we can regard it as such a tree:

```
a
/ | \
a A a
/ \ / \ / \
a b A b a b
/ \ / \ / \ / \ / \ / \
b 2 B 2 b 2 B 2 b 2
```

Then we can backtrack the tree and get all the results.

```
class Solution:
def letterCasePermutation(self, s: str) -> List[str]:
res = []
def backtrack(index, path):
if index == len(s): # if the index is equal to the length of the string, it means that we have traversed all the characters in the string
res.append("".join(path))
return
if s[index].isdigit(): # if the current character is a number, we can only continue to traverse
path.append(s[index]) # make a choice
backtrack(index + 1, path) # enter the next level of decision tree
path.pop() # cancel the choice
else: # if the current character is a letter, we can choose to convert it to uppercase or lowercase
path.append(s[index].lower()) # make a choice
backtrack(index + 1, path) # enter the next level of decision tree
path.pop() # cancel the choice
path.append(s[index].upper()) # make a choice
backtrack(index + 1, path) # enter the next level of decision tree
path.pop() # cancel the choice
backtrack(0, [])
return res
```

Complexity analysis:

- Time complexity: O (N \ * 2 ^ N), where N is the length of the string.
- Space complexity: O (N \ * 2 ^ N), where N is the length of the string.

test cases:

```
Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
Input: graph = [[1],[]]
Output: [[0,1]]
Input: graph = [[1,2,3],[2],[3],[]]
Output: [[0,1,2,3],[0,2,3],[0,3]]
Input: graph = [[1,3],[2],[3],[]]
Output: [[0,1,2,3],[0,3]]
```

The description of this problem is given a directed acyclic graph with n nodes, find all the paths from 0 to n-1 and output them (not in order).

The idea of this problem is also the idea of backtracking algorithm. We can regard each node as a tree. For example, when graph = [ [1, 2], [3], [3], []], we can regard it as such a tree:

```
0
/ | \
1 3 3
/ \ / \ / \
2 3 3 3 3 3
/ \ / \ / \ / \ / \ / \
3 3 3 3 3 3 3 3 3 3
```

Then we can backtrack the tree and get all the results.

```
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
res = []
def backtrack(index, path):
if index == len(graph) - 1: # if the index is equal to the length of the graph minus 1, it means that we have traversed all the nodes in the graph
res.append(path[:])
return
for i in graph[index]:
path.append(i) # make a choice
backtrack(i, path) # enter the next level of decision tree
path.pop() # cancel the choice
backtrack(0, [0])
return res
```

Complexity analysis:

- Time complexity: O (N \ * 2 ^ N), where N is the length of the graph.
- Space complexity: O (N \ * 2 ^ N), where N is the length of the graph.

test cases:

```
Input: "123456579"
Output: [123,456,579]
Input: "11235813"
Output: [1,1,2,3,5,8,13]
Input: "112358130"
Output: []
Input: "0123"
Output: []
Input: "1101111"
Output: [110, 1, 111]
```

The description of this problem is that given a numeric string S, such as S = "123456579", we can divide it into multiple Fibonacci sequences, such as [123, 456, 579]. A Fibonacci sequence is a sequence in which each number is the sum of the two preceding numbers. Formally, given a Fibonacci sequence, we want to delete at least one digit from it so that the remaining digits form a strictly increasing sequence. Returns all possible cases.

The idea of this problem is also the idea of backtracking algorithm, we can regard every number as a tree, for example, when S = "123456579", we can regard it as such a tree:

```
1
/ | \
2 2 2
/ \ / \ / \
3 3 3 3 3 3
/ \ / \ / \ / \ / \ / \
4 4 4 4 4 4 4 4 4 4
```

Then we can backtrack the tree and get all the results.

```
未完待续
```

test cases:

```
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: []
```

The description of this problem is to find all the shortest conversion sequences from begin word to end word given two words (beginWord and endWord) and a dictionary wordList. The conversion follows the following rules:

- Only one letter can be changed per conversion.
- The intermediate word in the conversion must be a dictionary word.

Of course we can use bfs to do it, everything is stored in the queue, but this will MLE:

```
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList):
if not endWord or not beginWord or not wordList or endWord not in wordList or beginWord == endWord:
return []
graph = collections.defaultdict(list)
for word in wordList:
for i in range(len(beginWord)):
graph[word[:i] + "*" + word[i+1:]].append(word)
print(graph)
ans = []
q = collections.deque([(beginWord, [beginWord])])
visited = set()
visited.add(beginWord)
while q and not ans:
length = len(q)
localvisited = set()
for _ in range(length):
word, path = q.popleft()
for i in range(len(beginWord)):
candidate = word[:i] + "*" + word[i+1:]
for nxt in graph[candidate]:
if nxt == endWord:
ans.append(path + [endWord])
if nxt not in visited:
localvisited.add(nxt)
q.append((nxt, path + [nxt]))
visited = visited.union(localvisited)
return ans
```

The better idea of this problem is also the idea of backtracking algorithm. We can think of every word as a tree, such as beginWord = "hit", endWord = "cog". When wordList = [ "hot", "dot", "dog", "lot", 'log', "cog"], we can see a tree like this:

```
hit
/ | \
hot dot lot
/ \ / \ / \
dot lot dot lot dot lot
/ \ / \ / \ / \ / \ / \
dog cog dog cog dog cog dog cog
```

Then we can build the graph with BFS first, and then backtrack the graph to get all the results.

```
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList):
wordList.append(beginWord) # needs to add begin word into list for indexing (L126 already consider endword to be in the wordList)
indexes = self.build_indexes(wordList)
distance = self.bfs(endWord, indexes)
results = []
self.dfs(beginWord, endWord, distance, indexes, [beginWord], results)
return results
def build_indexes(self, wordList):
indexes = {}
for word in wordList:
for i in range(len(word)):
key = word[:i] + '%' + word[i + 1:]
if key in indexes:
indexes[key].add(word)
else:
indexes[key] = set([word])
return indexes
def bfs(self, end, indexes): # bfs from end to start
distance = {end: 0}
queue = deque([end])
while queue:
word = queue.popleft()
for next_word in self.get_next_words(word, indexes):
if next_word not in distance:
distance[next_word] = distance[word] + 1
queue.append(next_word)
return distance
def get_next_words(self, word, indexes):
words = set()
for i in range(len(word)):
key = word[:i] + '%' + word[i + 1:]
for w in indexes.get(key, []):
words.add(w)
return words
def dfs(self, curt, target, distance, indexes, path, results):
if curt == target:
results.append(list(path))
return
for word in self.get_next_words(curt, indexes):
if word not in distance: # if there is no a possible way in word ladder
return
if distance[word] != distance[curt] - 1:
continue
path.append(word)
self.dfs(word, target, distance, indexes, path, results)
path.pop()
```

]]>In the context of two-pointer problems, there are two types: disparate two pointers and identical two pointers.

Disparate two pointers generally refer to one pointer moving from left to right and another pointer moving from right to left. For example, in binary search, we use disparate two pointers.

Identical

]]>In the context of two-pointer problems, there are two types: disparate two pointers and identical two pointers.

Disparate two pointers generally refer to one pointer moving from left to right and another pointer moving from right to left. For example, in binary search, we use disparate two pointers.

Identical two pointers generally refer to both pointers moving from left to right or both moving from right to left. For example, in linked lists, we use identical two pointers.

Next, we will discuss various approaches using two pointers. Let's take a look!

**↓ Click on the problem title to directly navigate to the corresponding LeetCode page ↓**

The description of this problem is to determine whether a string is a palindrome.

Test cases:

```
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
```

We can solve this problem using two pointers. One pointer starts from the left, and the other pointer starts from the right. We compare the characters pointed to by the two pointers. If they are not equal, then the string is not a palindrome. If they are equal, we continue moving towards the center.

The code is as follows:

```
class Solution:
def isPalindrome(self, s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
```

Complexity analysis:

- Time complexity: O(n), because each character is traversed once.
- Space complexity: O(1), as only a constant number of variables are used.

The description of this problem is to determine whether a string is a palindrome after deleting at most one character.

Test cases:

```
Input: s = "aba"
Output: true
Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.
Input: s = "abc"
Output: false
```

We can solve this problem using two pointers. One pointer starts from the left, and the other pointer starts from the right. We compare the characters pointed to by the two pointers. If they are not equal, we have two options: delete the character pointed to by the left pointer or delete the character pointed to by the right pointer. Then, we check if the remaining string is a palindrome. If it is, we return true; otherwise, we return false.

The code is as follows:

```
class Solution:
def validPalindrome(self, s: str) -> bool:
start, end = 0, len(s) - 1
while start < end:
if s[start] != s[end]:
left = s[start: end]
right = s[start + 1: end + 1]
return left == left[::-1] or right == right[::-1]
start += 1
end -= 1
return True
```

Complexity analysis:

- Time complexity: O(n), because each character is traversed once.
- Space complexity: O(1), as only a constant number of variables are used.

The description of this problem is to determine whether a string is a subsequence of another string.

Test cases:

```
Input: s = "abc", t = "ahbgdc"
Output: true
Input: s = "axc", t = "ahbgdc"
Output: false
```

We can solve this problem using two pointers. One pointer starts from the left, and the other pointer starts from the right. We compare the characters pointed to by the two pointers. If they are equal, we move both pointers to the right. If they are not equal, we only move the pointer on the right. Finally, we check if the pointer on the left has reached the end of the string.

```
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
i, j = 0, 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1
j += 1
return i == len(s)
```

Complexity analysis:

- Time complexity: O(n), because each character is traversed once.
- Space complexity: O(1), as only a constant number of variables are used.

The description of this problem is to find two numbers in an array that add up to a specific target.

Test cases:

```
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
```

We can solve this problem using two pointers. One pointer starts from the left, and the other pointer starts from the right. We compare the sum of the two numbers pointed to by the two pointers with the target. If the sum is equal to the target, we return the indices of the two numbers. If the sum is greater than the target, we move the pointer on the right to the left. If the sum is less than the target, we move the pointer on the left to the right.

```
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
if numbers[left] + numbers[right] == target:
return [left + 1, right + 1]
elif numbers[left] + numbers[right] < target:
left += 1
else:
right -= 1
return [-1, -1]
```

Complexity analysis:

- Time complexity: O(n), because each number is traversed once.
- Space complexity: O(1), as only a constant number of variables are used.

The description of this problem is to find two lines that form a container with the most water.

test cases:

```
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
```

We can solve this problem using two pointers. One pointer starts from the left, and the other pointer starts from the right. We compare the area of the two lines pointed to by the two pointers. If the area is greater than the maximum area, we update the maximum area. Then, we move the pointer on the left to the right if the line pointed to by the pointer on the left is shorter than the line pointed to by the pointer on the right; otherwise, we move the pointer on the right to the left.

```
class Solution:
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
res = 0
while left < right:
res = max(res, min(height[left], height[right]) * (right - left))
if height[left] < height[right]:
left += 1
else:
right -= 1
return res
```

Complexity analysis:

- Time complexity: O(n), because each number is traversed once.
- Space complexity: O(1), as only a constant number of variables are used.

The description of this problem is to find all unique triplets in the array which gives the sum of zero.

Test cases:

```
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Input: nums = []
Output: []
Input: nums = [0]
Output: []
```

We can solve this problem using two pointers. One pointer starts from the left, and the other pointer starts from the right. We compare the sum of the three numbers pointed to by the two pointers with zero. If the sum is equal to zero, we add the three numbers to the result. If the sum is greater than zero, we move the pointer on the right to the left. If the sum is less than zero, we move the pointer on the left to the right.

```
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i in range(len(nums)):
if nums[i] > 0:
break
if i == 0 or nums[i - 1] != nums[i]:
self.twoSum(nums, i, res)
return res
def twoSum(self, nums: List[int], i: int, res: List[List[int]]):
seen = set()
j = i + 1
while j < len(nums):
complement = -nums[i] - nums[j]
if complement in seen:
res.append([nums[i], nums[j], complement])
while j + 1 < len(nums) and nums[j] == nums[j + 1]:
j += 1
seen.add(nums[j])
j += 1
```

We can also use "gap" as a board to seperate the array into two parts. The left part is the numbers that are less than the gap, and the right part is the numbers that are greater than the gap. We can use two pointers to find the two numbers that add up to the gap. If the sum of the two numbers is equal to the gap, we add the three numbers to the result. If the sum is greater than the gap, we move the pointer on the right to the left. If the sum is less than the gap, we move the pointer on the left to the right.

```
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
if not nums or len(nums) < 3:
return []
res = set()
for gap in range(1, len(nums) - 1):
left = 0
right = len(nums) - 1
while left < gap and right > gap:
if nums[left] + nums[gap] + nums[right] < 0: # move left pointer
left += 1
elif nums[left] + nums[gap] + nums[right] > 0: # move right pointer
right -= 1
else:
res.add((nums[left], nums[gap], nums[right]))
left += 1
right -= 1
return res
```

Complexity analysis:

- Time complexity: O(n^2), because each number is traversed once.
- Space complexity: O(n), as a set is used to store the result.

Hi, welcome! This is Zhanming Tian. You may call me Elliot as well. I'm now a graduated student with a master's degree from Carnegie Mellon University in Silicon Valley, The study life here is absolutely tough, peer pressure is also high enough to let me down. However! I'm still strong.

Throughout my career, I have gained extensive experience in various programming languages and frameworks such as Java, Python, C++, TypeScript, Golang, React, Django, and Spring Boot!

At TuSimple, I contributed to developing critical systems like the Autonomous Driving Management System and the Trip Preparation System, which thousands of users have widely adopted. My work not only improved their performance but also streamlined their operations. While at CMU, I had the opportunity to share my knowledge and passion as a teaching assistant. Additionally, I interned at China Mobile, contributing to developing a Big Data Sale System.

Regrettably, I recently faced a layoff from my previous position and am now actively seeking new opportunities. However, this setback has not dampened my enthusiasm for growth and learning. I am continuously exploring the latest technologies and trends to stay ahead of the curve.

I love making my own stuff: my blog, my website, my tour video, my programming, my photographs... Though I think barely anyone would view it, it is still a sort of infinite passion to me.

On this website, you are going to see all of my creations. Tech blogs and videos! Be my guest and enjoy!

I hope my graduate study at Carnegie Mellon University, or, say, in the United States will be a most torturous while pleasant and fruitful memory in my life.

If you want to go direct to my Chinese website, you are also welcome👇

]]>2018, the year I came to Hong Kong for one month. This city is incredibly large and crowded. The reason why I stayed here for such a long time is that I was learning the course: Television Studio Production at Hong Kong Baptist University. In my free time, I took this video...(kinda Vlog)

For China users, please direct to:

]]>BFS & DFS are the most common interview questions, they can solve one same questions with both solution. Let's go!

we trained the same question both with DFS & BFS!

- BFS

- Bullet Input: image = [[1,1,1],[1,1,

BFS & DFS are the most common interview questions, they can solve one same questions with both solution. Let's go!

we trained the same question both with DFS & BFS!

- BFS

- Bullet Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2
- Bullet Output: [[2,2,2],[2,2,0],[2,0,1]]
- Bullet Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.

Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.

Method 1: Do the task first then insert into queue!

```
import collections
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
if image[sr][sc] == newColor:
return image
rows, cols = len(image), len(image[0])
oldColor = image[sr][sc]
# first do the task! then insert base element
image[sr][sc] = newColor
q = deque()
q.append([sr,sc])
# loop until q cannot go further
while q:
i, j = q.popleft()
# find all possible direction for this point
for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
if 0 <= x < rows and 0 <= y < cols and image[x][y] == oldColor:
# first do! then insert surronding elements
image[x][y] = newColor
q.append([x, y])
return image
```

Method 2: insert into queue then do stuff!

```
import collections
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
if image[sr][sc] == newColor:
return image
rows, cols = len(image), len(image[0])
oldColor = image[sr][sc]
# insert base element first
q = deque()
q.append([sr,sc])
# loop until q cannot go further
while q:
i, j = q.popleft()
# do it here!
image[i][j] = newColor
# find all possible direction for this point
for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
if 0 <= x < rows and 0 <= y < cols and image[x][y] == oldColor:
# insert surrounding elements first!
q.append([x, y])
return image
```

- DFS

matrix DFS ALWAYS use recursion, tree DFS can use DFS recursion or stack!

```
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
# DFS ALWAYS start with a list of judgements for simplification
if image[sr][sc] == newColor:
return image
rows, cols = len(image), len(image[0])
# base and "always" operation
oldColor = image[sr][sc]
image[sr][sc] = newColor
# recursion around all surronding (REMEBER To set up stop condition)
for x, y in (sr, sc + 1), (sr + 1, sc), (sr - 1, sc), (sr, sc - 1):
if 0 <= x < rows and 0 <= y < cols and image[x][y] == oldColor:
self.floodFill(image, x, y, newColor)
return image
```

- DFS

```
import collections
def numIslands(self, grid: List[List[str]]) -> int:
rows = len(grid)
cols = len(grid[0])
count = 0
def bfs(grid, m, n):
res = 0
if grid == None: return res
q = deque()
q.append((m, n))
grid[m][n] = "#"
while q:
curNode = q.popleft()
for x, y in (curNode[0] + 1, curNode[1]), (curNode[0], curNode[1] + 1), (curNode[0] - 1, curNode[1]), (curNode[0], curNode[1] - 1):
if 0 <= x < rows and 0 <= y < cols and grid[x][y] == "1":
grid[x][y] = "#"
q.append((x, y))
for row in range(rows):
for col in range(cols):
if grid[row][col] == "1":
bfs(grid, row, col)
count += 1
return count
```

- BFS

```
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(grid, i, j):
if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
return
grid[i][j] = '#' # THE MOST IMPORTANT STEP, VISITED STEP
dfs(grid, i+1, j)
dfs(grid, i-1, j)
dfs(grid, i, j+1)
dfs(grid, i, j-1)
if not grid:
return 0
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
dfs(grid, i, j)
count += 1
return count
```

https://assets.leetcode.com/uploads/2021/03/31/maze1-1-grid.jpg

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]

Output: true

Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.

- BFS

```
import collections
import collections
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
rows = len(maze)
cols = len(maze[0])
dir = [1, 0, -1, 0, 1]
visited = [[0 for _ in range(cols)] for _ in range(rows)]
q = deque()
q.append(start)
visited[start[0]][start[1]] = 1
while q:
cur = q.popleft()
if cur[0] == destination[0] and cur[1] == destination[1]:
return True
for i in range(4):
newX = cur[0]
newY = cur[1]
while 0 <= newX < rows and 0 <= newY < cols and maze[newX][newY] != 1:
newX += dir[i]
newY += dir[i + 1]
newX -= dir[i]
newY -= dir[i + 1]
if visited[newX][newY]: continue
q.append([newX, newY])
visited[newX][newY] = 1
return False
```

https://assets.leetcode.com/uploads/2021/03/31/maze1-1-grid.jpg

- Bullet Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
- Bullet Output: 12
- Bullet Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.

The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

- BFS

```
import collections
def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
rows = len(maze)
cols = len(maze[0])
dir = [1, 0, -1, 0, 1]
res = [[float('inf') for _ in range(cols)] for _ in range(rows)]
q = deque()
q.append([start[0], start[1], 0])
while q:
cur = q.popleft()
if cur[2] >= res[cur[0]][cur[1]]:
continue
res[cur[0]][cur[1]] = cur[2]
for i in range(4):
newX = cur[0]
newY = cur[1]
path = cur[2]
while 0 <= newX < rows and 0 <= newY < cols and maze[newX][newY] == 0:
newX += dir[i]
newY += dir[i + 1]
path += 1
newX -= dir[i]
newY -= dir[i + 1]
path -= 1
q.append([newX, newY, path])
return -1 if res[destination[0]][destination[1]] == float('inf') else res[destination[0]][destination[1]]
```

Solution 1

Input: nums = [1,2,3]

Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

```
def subsets(self, nums: List[int]) -> List[List[int]]:
def backtract(sublist, templist, nums, start):
sublist.append(templist[:])
for i in range(start, len(nums)):
templist.append(nums[i])
backtract(sublist, templist, nums, i + 1)
templist.pop()
return sublist
sublist = []
nums.sort()
return backtract(sublist, [], nums, 0)
```

Solution 2

```
def subsets(self, nums):
result = [[]]
for num in nums:
result += [i + [num] for i in result]
return result
```

Input: nums = [1,2,2]

Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

```
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
def backtract(sublist, templist, nums, start):
sublist.append(templist[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue
templist.append(nums[i])
backtract(sublist, templist, nums, i + 1)
templist.pop()
return sublist
sublist = []
nums.sort()
return backtract(sublist, [], nums, 0)
```

Input: nums = [1,2,3]

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

```
def backtract(self, reslist, templist, nums) -> List[List[int]]:
if len(templist) == len(nums):
reslist.append(templist[:])
else:
for i in range(len(nums)):
if nums[i] in templist:
continue
templist.append(nums[i])
self.backtract(reslist, templist, nums)
templist.pop()
return reslist
def permute(self, nums: List[int]) -> List[List[int]]:
reslist = []
nums.sort()
return self.backtract(reslist, [], nums)
```

Input: nums = [1,1,2]

Output:

[[1,1,2],

[1,2,1],

[2,1,1]]

```
def backtract(self, reslist, templist, nums, used) -> List[List[int]]:
if len(templist) == len(nums):
reslist.append(templist[:])
else:
for i in range(len(nums)):
if used[i] == 1 or i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
used[i] = 1
templist.append(nums[i])
self.backtract(reslist, templist, nums, used)
used[i] = 0
templist.pop()
return reslist
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
reslist = []
boolean = [0 for _ in range(len(nums))]
nums.sort()
return self.backtract(reslist, [], nums, boolean)
```

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.

```
def backtrack(self, reslist, templist, nums, remain, start) -> List[List[int]]:
if remain < 0:
return
elif remain == 0:
reslist.append(templist[:])
else:
for i in range(start, len(nums)):
templist.append(nums[i])
self.backtrack(reslist, templist, nums, remain - nums[i], i)
templist.pop()
return reslist
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
reslist = []
candidates.sort()
return self.backtrack(reslist, [], candidates, target, 0)
```

Input: candidates = [10,1,2,7,6,1,5], target = 8

Output:

[

[1,1,6],

[1,2,5],

[1,7],

[2,6]

]

```
def backtrack(self, reslist, templist, nums, remain, start) -> List[List[int]]:
if remain < 0:
return
elif remain == 0:
reslist.append(templist[:])
else:
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue
templist.append(nums[i])
self.backtrack(reslist, templist, nums, remain - nums[i], i + 1)
templist.pop()
return reslist
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
reslist = []
candidates.sort()
return self.backtrack(reslist, [], candidates, target, 0)
```

Input: s = "aab"

Output: [["a","a","b"],["aa","b"]]

https://leetcode.com/problems/palindrome-partitioning/Figures/131/time_complexity.png

```
def isPalindrome(self, s, start, end) -> bool:
temp = s[start:end + 1]
return temp == temp[::-1]
def backtrack(self, reslist, templist, s, start) -> List[List[int]]:
if start == len(s):
reslist.append(templist[:])
else:
for i in range(start, len(s)):
if self.isPalindrome(s, start, i):
templist.append(s[start: i + 1])
self.backtrack(reslist, templist, s, i + 1)
templist.pop()
return reslist
def partition(self, s: str) -> List[List[str]]:
reslist = []
return self.backtrack(reslist, [], s, 0)
```

- Binary Tree Level Order Traversal

Why this is wrong?

```
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
import collections
if root == None: return res
res = []
q = deque()
q.append(root)
while q:
temp = q.popleft()
res.append(temp.val)
if temp.left != None:
q.append(temp.left)
if temp.right != None:
q.append(temp.right)
return res
```

Use your level

```
import collections
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
if root == None: return res
q = deque()
q.append(root)
while q:
# SIZE! OF! THE! QUEUE!
size = len(q)
curLevel = []
for i in range(size):
curNode = q.popleft()
curLevel.append(curNode.val)
if curNode.left != None:
q.append(curNode.left)
if curNode.right != None:
q.append(curNode.right)
res.append(curLevel)
return res
```

- Binary Tree Zigzag Level Order Traversal

```
import collections
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
if root == None: return res
q = deque()
q.append(root)
counter = 0
while q:
curLevel = []
for i in range(len(q)):
curNode = q.popleft()
curLevel.append(curNode.val)
if curNode.left:
q.append(curNode.left)
if curNode.right:
q.append(curNode.right)
if counter % 2 == 0:
res.append(curLevel)
else:
res.append(curLevel[::-1])
counter += 1
return res
```

- Validate Binary Search Tree

Template of inorder traversal

```
def isValidBST(self, root: Optional[TreeNode]) -> bool:
if root == None: return True
stack = []
ls = []
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
# condition here
root = stack.pop()
ls.append(root.val)
root = root.right
return ls
```

Inorder traversal

```
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
if root == None: return True
stack = []
pre = None
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
# greater or equal than!
if pre and pre.val >= root.val:
return False
pre = root
root = root.right
return True
```

dfs

```
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def isValidBST(root, minValue, maxValue):
if root == None: return True
if root.val >= maxValue or root.val <= minValue:
return False
return isValidBST(root.left, minValue, root.val) and isValidBST(root.right, root.val, maxValue)
return isValidBST(root, -sys.maxsize, sys.maxsize)
```

- Kth Smallest Element in a BST

```
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
if root == None: return -1
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
if k == 1: return root.val
k -= 1
root = root.right
return -1
```

- Flatten Binary Tree to Linked List

```
def flatten(self, root: Optional[TreeNode]) -> None:
def dfs(root):
if root == None: return None
leftLast = dfs(root.left)
rightLast = dfs(root.right)
if leftLast:
############
leftLast.right = root.right
root.right = root.left
root.left = None
############
if rightLast != None:
return rightLast
if leftLast != None:
return leftLast
return root
dfs(root)
```

- Binary Tree Right Side View

Why this is wrong?

```
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
res = []
if root == None: return res
q = collections.deque()
q.append(root)
res.append(root.val)
while q:
for i in range(len(q)):
curNode = q.popleft()
if i == len(q) - 1:
res.append(curNode.val)
if curNode.left:
q.append(curNode.left)
if curNode.right:
q.append(curNode.right)
return res
```

It should be:

```
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
res = []
if root == None: return res
q = collections.deque()
q.append(root)
while q:
size = len(q)
for i in range(size):
curNode = q.popleft()
if curNode.left:
q.append(curNode.left)
if curNode.right:
q.append(curNode.right)
if i == size - 1:
res.append(curNode.val)
return res
```

dfs

```
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
def dfs(root, depth, res):
if root == None: return
if depth == len(res):
res.append(root.val)
dfs(root.right, depth + 1, res)
dfs(root.left, depth + 1, res)
res = []
dfs(root, 0, res)
return res
```

]]>For China user:

]]>Singapore is one of the best place I've ever been! I love there so much that bring me a lot in memory.

For China user:

]]>Anyway, Let's start STRING GAMES!

Let's start with some basic (not that basic) operations on String by Python:

0. Stack!!!

You should be aware that **Most of the String problems** is associate with stack!

That's right!

]]>String matters, especially in interview questions and Leetcode!

Anyway, Let's start STRING GAMES!

Let's start with some basic (not that basic) operations on String by Python:

0. Stack!!!

You should be aware that **Most of the String problems** is associate with stack!

That's right! sometimes we tend to use operations quite similar to compiler, thus we need to be familiar with everything in **STACK**

Stack operations

```
stack = []
# push into stack
stack.append(1) # [1]
stack.append(2) # [1, 2]
stack.append(3) # [1, 2, 3]
# pop out the top element
top = stack.pop() # top = 3, stack -> [1, 2]
# get the top element
top = stack[-1] # top = 2, stack -> [1, 2] (similar to peek)
```

But in fact, how we use python queue in leetcode problem is that:

a) We use head-tail linked list (deque):

```
from collections import deque
de1 = deque()
de1.append(1) # [1]
de1.append(2) # [1, 2]
de1.appendleft(5) # [5, 1, 2]
de1.appendleft(6) # [6, 5, 1, 2]
print(de1.count(1)) # 1 appears 1
de1.reverse() # [2, 1, 5, 6]
de1.extend([444, 555, 666]) # [2, 1, 5, 6, 444, 555, 666]
de1.pop() # [2, 1, 5, 6, 444, 555]
de1.popleft() # [1, 5, 6, 444, 555]
```

b) Priority queue:

```
import queue
q = queue.Queue()
q.put(3)
q.put(5)
q.put(4)
full = q.full() # True
while not q.empty():
print(q.get()) # [3, 5, 4]
# min first
pq = queue.PriorityQueue()
pq.put(3)
pq.put(5)
pq.put(4)
while not pq.empty():
print(pq.get()) # [3, 4, 5]
# max first
pq = []
pq.append(3)
pq.append(5)
pq.append(4)
pq.sort(reverse=1)
while pq:
print(pq.pop())
```

By the way, we should know how to implement a queue through **2 stack**, which will be push = O(1) and pop = O(1)

This is the problem of Leetcode 232:

```
class MyQueue:
def __init__(self):
self.LI = [] # Last In
self.FO = [] # First Out
def push(self, x):
self.LI.append(x)
def pop(self):
if not self.FO:
while self.LI:
self.FO.append(self.LI.pop())
return self.FO.pop()
def peek(self):
if not self.FO:
return self.LI[0]
else:
return self.FO[-1]
def empty(self):
return not self.LI and not self.FO
```

Or if we want one stack to represent queue, it is also OK!

```
class MyQueue(object):
def __init__(self):
self.st = []
def push(self, x):
if len(self.st) == 0:
self.st.append(x)
return
tmp = self.st.pop(-1)
self.push(x)
self.st.append(tmp)
def pop(self):
return self.st.pop(-1)
def peek(self):
return self.st[-1]
def empty(self):
return len(self.st) == 0
```

- Reverse String:

```
ori_str = "abcd"
reverse_str = ori_str[::-1] #come to "dcba"
```

- Find SubString:

```
super_str = "abcde"
sub_str = "bc"
not_sub_str = "abd"
pos = super_str.find(sub_str) #pos = 1, find from beginning
pos_2 = super_str.rfind(sub_str) # pos_2 = 1, find from the rear
pos_3 = super_str.find(not_sub_str) # pos_2 = -1, not substring found
```

- index & count

```
ori_str = "abcde"
pos = ori_str.index("c") # pos = 2
pos_1 = ori_str.rindex("b") # pos_1 = 1
```

- count

```
ori_str = "abcdeaa"
num = ori_str.count("a") # num = 3
num_1 = ori_str.count("a", 0, 3) # num_1 = 1
```

- Split, Partition, Split with line

```
str = "123123123"
str_list = str.split('2') # ['1', '31', '31', '3']
str_tuple = str.partition('2') # ('1', '2', '3123123')
str='abc\nabc\nabc\nabc'
str_list = str.splitlines() # ['abc', 'abc', 'abc', 'abc']
```

- Judgement

```
str0='0123abcd'
str1='12345'
str2='abcdef'
str3=' '
str0.startswith('0') # check if start with 0, True
str0.endswith('0') # check if end with 0, False
str1.isalnum() # check if the str all consist of alphabet and number, True
str2.isalpha() # check if the str all consist of alphabet, True
str0.isdigit() # check if the str all consist of digit, False
str3.isspace() # check if all consist of space, True
```

- ATTENTION: String cannot be changed, but we can change by..

```
str0 = "what"
# str0[2] = "i" # This is not allowed!!!
list_str0 = list(str0)
list_str0[2] = "i"
str0 = "".join(list_str0)
print(str0)
```

- Mapping

```
date = "2019-8-15"
Y, M, D = map(int, date.split('-'))
# Y = 2019, M = 8, D = 15
```

Description: return true if `s`

is an anagram of `t`

```
Input: s = "anagram", t = "nagaram"
Output: true
```

Solution 1 with Collections (inner Hash Map):

```
def isAnagram(self, s: str, t: str) -> bool:
from collections import Counter
# Counter(s) = Counter({'a': 3, 'n': 1, 'g': 1, 'r': 1, 'm': 1})
return Counter(s) == Counter(t)
```

Solution 2 with HashMap (By ourself) in O(n):

```
def isAnagram(self, s: str, t: str) -> bool:
map1 = {}
if s == '' and t == '':
return True
if len(s) != len(t):
return False
for itr in range(len(s)):
map1[s[itr]] = map1.setdefault(s[itr], 0) + 1
map1[s[itr]] = map1.setdefault(t[itr], 0) + 1
for i in map1.values():
if i != 0:
return False
return True
```

Solution 1 with Hash Map:

```
def longestPalindrome(self, s: str) -> int:
map1 = {}
for item in range(len(s)):
map1[s[item]] = map1.setdefault(s[item], 0) + 1
res = 0
for item in map1.values():
res += (item // 2) * 2
if res < len(s):
res += 1
return res
```

Description:

Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Solution 1 with find function:

```
def isIsomorphic(self, s, t):
# e.g. s = "eggggwe"
# [s.find(i) for i in s] = [0, 1, 1, 1, 1, 5, 0]
return [s.find(i) for i in s] == [t.find(j) for j in t]
```

Solution 2 with dict function:

```
def isIsomorphic(self, s, t):
if len(s) != len(t): return False
map1 = {}
for i in range(len(s)):
if s[i] in map1:
if map1[s[i]] != t[i]:
return False
elif t[i] in map1.values():
return False
else:
map1[s[i]] = t[i]
return True
```

```
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
```

Solution 1 with find function:

```
res = 0
def countSubstrings(self, s: str) -> int:
for i in range(len(s)):
self.extension(s, i, i);
self.extension(s, i, i+1);
return self.res
def extension(self, s: str, start: int, end: int):
while start >= 0 and end <= len(s) - 1 and s[start] == s[end]:
start -= 1
end += 1
self.res += 1
```

```
Input: x = 121
Output: true
Input: x = -121
Output: false
Could you solve it without converting the integer to a string?
```

Solution 1 simple implement:

```
def isPalindrome(self, x: int) -> bool:
if x < 0 or (x > 0 and x % 10 == 0): return False
ori = x
res = 0
while x != 0:
digit = x % 10
x = x // 10
res = digit + res * 10
return ori == res
```

Solution 2 with half loop:

```
def isPalindrome(self, x: int) -> bool:
if x < 0 or (x > 0 and x % 10 == 0): return False
right = 0
while x > right:
right = right * 10 + x % 10
x = x // 10
return x == right or x == right // 10
```

```
Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".
```

Solution 1 with group by character:

```
def countBinarySubstrings(self, s: str) -> int:
groups = [1]
for i in range(1, len(s)):
if s[i] != s[i - 1]:
groups.append(1)
else:
groups[-1] += 1
ans = 0
for i in range(1, len(groups)):
ans += min(groups[i-1], groups[i])
return ans
```

Solution 1 with linear scanning, not using a list, but use two var to store pre and cur:

```
def countBinarySubstrings(self, s: str) -> int:
preLen, curLen, count = 0, 1, 0
for i in range(1, len(s)):
if s[i] == s[i - 1]:
curLen += 1
else:
preLen = curLen
curLen = 1
if preLen >= curLen:
count += 1
return count
```

]]>Fortunately, I got the experience to go to have a course in HKBU..

Here is what happened ?

For China user:

]]>Bit operation plays a cardinal role in the fundamental calculation in machine-level language. I'm currently enrolled at Carnegie Mellon University as a master student in the Software Engineering program. One of the renowned courses must be "Introduction to Computer System".

After the first lab, namely Datalab. I spent enormous time on bit-level calculation and practice. To recall what I learned, how it was used in the practice of leetcode, here give the two parts: tricks & corresponding leetcode problems.

Bit operations contain the following:

&, |, ^, ~, <<, >>, !

In the above operation, I love shift and XOR operations. Why?

Let's see what can they do!

Mask is quite crucial in bit computation. This is set to 0 since all the bit operation always depend on MASKS!

Here are a list of masks that is quite useful:

(I use int type here)

```
# a) obtain FFFFFFFF
mask_FFFFFFFF = ~0
# b) obtain 0000FFFF
mask_0000FFFF = 1 << 16 - 1
# c) obtain FFFF0000
mask_0000FFFF = ~0 << 16
# d) obtain 55555555
mask_55555555 = "Not Available now"
```

```
# gives u * 2^3
u << 3
# gives u * 24
(u << 5) - (u << 3)
```

Remember that this is also good when u is a negative number. (But not the case on the boundary of type)

such as:

```
# good case
u = -1 # u = 0xFFFFFFFF --- u = -1
u <<= 1 # u = 0xFFFFFFFE --- u = -2
u <<= 1 # u = 0xFFFFFFFC --- u = -4
```

Consider the bad case as always!

```
#bad case
u = 2147483648 # u = 0x7FFFFFFF
u << 1 # u = 0xFFFFFFFF
v = -2147483648 # v = 0x10000000
v << 1 # v = 0x00000000
```

In the right shift, it is not always rational divided due to rounding, it is quite similar to `5/2 = 2`

in C.

Notice that we should consider positive and negative cases separately.

For positive cases:

For negative cases:

It is wrong, because in negative cases, we should round up rather round down! So we need to change the right shift code to:

```
# this denote for if x is a negative number of divide 2 with rounding
x = -5
x = x + (1 << k) - 1) >> k
# In this way, it is similar to x >> k in positive number
```

Eliminate the last 1 in binary

n & (n - 1)

```
01011101 &
01011100
--------
01011100
```

Obtain the last 1 in binary

n & (-n)

```
10110100 &
01001100
--------
00000100
```

```
x ^ 0 = x
x ^ x = 0
x ^ -1 = ~x
```

Description: get the numbers of bit differences in binary

```
Input: x = 1, y = 4
Output: 2
Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
```

Solution 1 with O(n):

```
def hammingDistance(self, x: int, y: int) -> int:
temp = x ^ y #get the diff numbers
count = 0
while temp != 0:
temp &= temp - 1 #eliminate 1 at a time
count += 1
return count
```

Solution 2 with special function in O(n):

```
def hammingDistance(self, x: int, y: int) -> int:
bin(x ^ y).count('1')
```

Solution 3 (Fastest!) with shift in O(n):

```
def hammingDistance(self, x, y):
res = x ^ y
counter = 0
for i in range(32):
if res >> i & 1 == 1: #using shift is much faster!!!!!
counter += 1
return counter
```

Description: find the number in the list that is single

```
Input: [4,1,2,1,2]
Output: 4
```

Solution 1 with O(n):

Consider that:

```
x ^ x = 0
x ^ 0 = x
```

Then use loooooop for entire list, the operation would be:

```
4 ^ 1 ^ 2 ^ 1 ^ 2 => 4
```

Thus, the solution would be:

```
def singleNumber(self, nums: List[int]) -> int:
res = 0
for item in nums:
res ^= item
return res
```

Input: [3,0,1]

Output: 2

Solution 1 use XOR in O(1):

```
def missingNumber(self, nums: List[int]) -> int:
ret = 0
for i in range(len(nums)):
ret ^= i ^ nums[i]
return ret ^ len(nums) # I love this one!
```

Why?

Consider that:

`ret = (0 ^ 3) ^ (1 ^ 0) ^ (2 ^ 1)`

and return `len(nums)`

if `ret = 0`

return `ret`

if `ret != 0`

Solution 2 use enumerate in O(1):

```
def missingNumber(self, nums: List[int]) -> int:
nums.sort()
for index, item in enumerate(nums):
if index != item:
return index
else: # else is a good usage for "for"
return nums[-1] + 1
```

Solution 1: that is **not** using bit operation, but I like it pretty much, since it use the set() to eliminate duplicates, btw, this solution is also suitable for the above problem 136:

```
def singleNumber(self, nums: List[int]) -> List[int]:
res = set()
for item in nums:
if item in res: res.remove(item)
else: res.add(item)
return res
```

Solution 2: bit operation solution:

```
# The bitmask will have all the differences between x and y (the two singles).
# x has 0 and y has 1 or vice-versa in those bits.
# You take one difference, the rightmost one.
# Iterate through array again dividing into two.
# The ones which has 1 on the rightmost different bit into one group and those who have 0 into another group.
# Group1 : [x^a^a^b^b] = x
# Group2 : [y^c^c^d^d] = y
# bitmask^x = y;
def singleNumber(self, nums: List[int]) -> List[int]:
bitmask = 0
for num in nums:
bitmask ^= num
diff = bitmask & (-bitmask)
x = 0
for num in nums:
if num & diff:
x ^= num
return [x, bitmask ^ x]
```

Solution 1: again, here I would like to reverse the bits by using the smart reverse method in python:

```
def reverseBits(self, n: int) -> int:
return int('{:032b}'.format(n)[::-1], 2)
```

`{:032b}'.format(n)`

is for revert int value to string with 32 bit binary

`[::-1]`

is the smart way to reverse a string in Python

`int(x, 2)`

is to output the int value as a binary number

Solution 2:

```
def reverseBits(self, n: int) -> int:
ret, power = 0, 31
while n:
ret += (n & 1) << power
n >>= 1
power -= 1
return ret
```

Solution: use eliminate last 1 method:

KEY POINT: Remember to consider 0!!!

```
def isPowerOfTwo(self, n: int) -> bool:
return n > 0 and (n & (n - 1)) == 0
```

Solution:

```
def isPowerOfFour(self, n: int) -> bool:
if(n<0):
return False
b = bin(n)
if(b.count("1") == 1 and (b[3:].count("0") % 2 == 0)):
return True
return False
```

Solution 1:

```
def hasAlternatingBits(self, n: int) -> bool:
return n & (n >> 1) == 0 and n & (n >> 2) == n >> 2
```

Solution 2:

```
def hasAlternatingBits(self, n: int) -> bool:
# 10101010101
# + 1010101010 ( number >> 1 )
# ---------------
# = 11111111111
# & 100000000000
# ---------------
# = 0 ( power of two )
n = n ^ (n >> 1)
return n & n + 1 == 0
```

]]>This is the pre-assignment of 18-652 Foundation of Software Engineering in CMU. Tech used:

Front-end:

- HTML/CSS, Bootstrap 5, JQuery(JavaScript), EJS

Back-end:

- Node.js, Express.js, Socket.io, express-session, bcrypt.js

Try this now!!!

Introduction video of this project:

]]>