Description
https://leetcode.com/problems/letter-case-permutation/
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:
swill be a string with length between1and12.swill consist only of letters or digits.
Explanation
Use the backtracking approach to build permutations. If the character is an alphabetical letter, build permutation in both uppercase or lowercase.
Python Solution
class Solution:
def letterCasePermutation(self, s: str) -> List[str]:
results = []
self.helper(results, s, "", 0)
return results
def helper(self, results, s, permutation, start):
if len(permutation) == len(s):
results.append(permutation)
return
if s[start].isalpha():
self.helper(results, s, permutation + s[start].upper(), start + 1)
self.helper(results, s, permutation + s[start].lower(), start + 1)
else:
self.helper(results, s, permutation + s[start], start + 1)
- Time Complexity: O(N).
- Space Complexity: O(N).