784. Letter Case Permutation

Problem Statement

link: LeetCode.cn LeetCode

Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. Return the output in any order.

Example:

Input: s = "a1b2" Output: ["a1b2","a1B2","A1b2","A1B2"]

Input: s = "3z4" Output: ["3z4","3Z4"]

Solution Approach

The algorithm uses a breadth-first search (BFS) approach to generate all possible letter case permutations by systematically exploring each character’s uppercase and lowercase options.

Algorithm

1. Breadth-First Search (BFS): The algorithm uses BFS to explore all possible permutations of the string by processing each character’s uppercase and lowercase variations.
2. Character Case Handling: For each character in the string, it generates new permutations by either maintaining the current case or swapping the case if the character is alphabetic.
3. Queue for Permutations: A queue is employed to manage and expand permutations incrementally, ensuring that all combinations are explored before finalizing the results.

   Complexity

   time complexity: O(n * 2^n) space complexity: O(n * 2^n )

Implement

    class Solution:
    def letterCasePermutation(self, S: str) -> List[str]:
        res = ['']
        for c in S:
            if c.isalpha():
                res = [i + j for i in res for j in [c.upper(), c.lower()]]
            else:
                res = [i + c for i in res]
        return res
        
class Solution:
  def letterCasePermutation(self, s: str) -> List[str]:
      ans = []
      q = deque([''])
      while q:
          cur = q[0]
          pos = len(cur)
          if pos == len(s):
              ans.append(cur)
              q.popleft()
          else:
              if s[pos].isalpha():
                  q.append(cur + s[pos].swapcase())
              q[0] += s[pos]
      return ans

    
    

Twitter  facebook  Email