186. Letter Case Permutation

Medium · Backtracking

Given a string containing letters and digits, return all possible strings that can be created by converting each letter to either uppercase or lowercase. Digits remain unchanged.

The order of results does not matter, but each permutation should appear exactly once.

Examples

Example 1
Input: "a1b2"
Output: ["a1b2", "a1B2", "A1b2", "A1B2"]
Explanation: We have 2 letters (a, b) that can each be uppercase or lowercase, giving 2² = 4 permutations. The digit 1 and 2 stay the same in all permutations.
Example 2
Input: "3z4"
Output: ["3z4", "3Z4"]
Explanation: Only one letter (z) can change case, so we get 2¹ = 2 permutations. The digits 3 and 4 remain unchanged.

Constraints