Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string.
Return a list of all possible strings we could create. You can return the output in any order.
Example 1:
Input: S = "a1b2" Output: ["a1b2","a1B2","A1b2","A1B2"]
Example 2:
Input: S = "3z4" Output: ["3z4","3Z4"]
Example 3:
Input: S = "12345" Output: ["12345"]
Example 4:
Input: S = "0" Output: ["0"]
Constraints:
S will be a string with the length between 1 and 12.S will consist only of letters or digits.
The description was taken from https://leetcode.com/problems/letter-case-permutation/.
#O(2^N) Time, O(2^N) Space
class Solution:
def letterCasePermutation(self, S: str) -> List[str]:
letters = 'AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz'
output = []
def backtrack(combo:str, start:int) -> None:
if start == len(S):
output.append("".join(combo))
return if S[start] in letters:
combo.append(S[start].upper())
backtrack(combo, start + 1)
combo.pop()
combo.append(S[start].lower())
backtrack(combo, start+1)
combo.pop()
else:
combo.append(S[start])
backtrack(combo, start + 1)
combo.pop()
backtrack([], 0)
return outputIf a problem requires us to return all possible combinations of a given input, typically that is an indication that backtracking is a good approach.
Backtracking is a Depth-First Search algorithm where we remove a choice whenever the DFS path yoyo returns to the given function. This allows us to circulate elements into each valid position so that we can generate each valid combination.
A general template for backtracking is to set a base case that appends a valid combination for a given DFS path to the output, if not, check if a placement is valid, then make the placement. Once that placement is made, we'd go down a new DFS path with that placement and if that path didn't lead to a solution or it didn't lead to every solution like in this problem, we'd backtrack on the choice to make that placement by removing it from the combination.
From the problem description, we can see that each letter provides an additional option for a combination: an uppercase state or a lowercase state.
To generate all of these choices, within a function call, we will see if the current character is a letter or digit. If it is a letter, we will create two new DFS paths with a lowercase and uppercase character placement. If it is a digit, we will just place the character and continue down that DFS path.
Let's start by creating a lookup string of each letter.
We could have chosen to instead use the built-in .isAlpha() function for our lookups but this is how we'd do it by hand.
letters = 'AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz'
We will also need an output array that we'll append each valid combination to.
output = []
Next, we'll create our recursive backtrack function.
The function will take a substring combination of the given DFS path and a starting index which will be the left bound for the substring the DFS path is generating.
def backtrack(combo:str, start:int) -> None:
As mentioned in the beginning, we'll set a base case to see if we have a valid combination.
We'll know this is true if the starting index is equal to the length of the string because that would mean we have placed all of the characters we needed to.
If that is the case, we will join the characters together to form a string then append the string to the output array and return from this DFS path.
if start == len(S):
output.append("".join(combo))
return
Otherwise, we will keep making placements within the current DFS path.
Our placements will depend on the current start index that we are given. If the index is a letter, then we have two paths we need to exhaust; an uppercase state and a lowercase state.
if S[start] in letters:
We'll place an uppercase version of the letter to our current combination and continue down the path with that letter placement.
combo.append(S[start].upper())
backtrack(combo, start + 1)
Once our DFS yoyo has returned back to this function call, we will backtrack on our decision to place this uppercase letter and pop it from the combination.
combo.pop()
This will allow us to circulate in a lowercase version of the letter and continue down the DFS path with that letter in this index instead.
That is pretty much the point of backtracking, we pop and push letters into different spots so that we can generate different combinations.
combo.append(S[start].lower())
backtrack(combo, start+1)
combo.pop()
If the current character is a number instead, we will just place it into the current combination and continue down the DFS path with the number in this starting index.
else:
combo.append(S[start])
backtrack(combo, start + 1)
combo.pop()
Now that we have our backtrack function built, we just need to make the initial call with an empty combination and starting index of zero.
Once the output has been filled with each valid combination, we will return it.
backtrack([], 0)
return output