LeetCode 784. 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"]


  • s will be a string with length between 1 and 12.
  • s will consist only of letters or digits.


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):    
        if s[start].isalpha():
            self.helper(results, s, permutation + s[start].upper(), start + 1)
            self.helper(results, s, permutation + s[start].lower(), start + 1)            
            self.helper(results, s, permutation + s[start], start + 1)
  • Time Complexity: O(N).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published. Required fields are marked *