LeetCode 784. Letter Case Permutation

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:

  • s will be a string with length between 1 and 12.
  • s will 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).

Leave a Reply

Your email address will not be published.