What algorithm or data structure is used to solve Letter Case Permutation?

Letter Case Permutation uses the following concepts: String, Backtracking, Bit Manipulation. The recommended patterns to study are: .

Letter Case Permutation — LeetCode #784 (Medium)

Tags: String, Backtracking, Bit Manipulation

Related patterns:

Brute Force approach

Time complexity: O(n²). Space complexity: O(1).

The brute-force approach generates all possible combinations of the string by treating each letter independently. For each letter, we can either keep it as is or change its case, leading to a combinatorial explosion of possibilities.

The time complexity is O(n²) because for each character, we might create two branches in the recursion tree, leading to 2^n combinations, and each combination takes O(n) time to build.

Step 1: Initialize a list to store all permutations.
Step 2: Use a recursive function to explore each character in the string.
Step 3: For each character, if it's a letter, branch into two recursive calls: one with the lowercase and one with the uppercase version.
Step 4: If it's a digit, simply continue to the next character without changing it.
Step 5: When reaching the end of the string, add the current permutation to the list.

Input: 'a1b2' 1. Start with index 0, path = '' 2. Choose 'a' -> path = ['a'] 3. Choose '1' -> path = ['a', '1'] 4. Choose 'b' -> path = ['a', '1', 'b'] 5. Choose '2' -> path = ['a', '1', 'b', '2'] -> Add 'a1b2' to results 6. Backtrack to explore 'A' -> path = ['A', '1', 'b', '2'] -> Add 'A1b2' to results.

#784

Letter Case Permutation

Medium

String↗Backtracking↗Bit Manipulation↗

LeetCode ↗

Approaches

💡

Intuition

Time O(n²)Space O(1)

⚙️

Algorithm

5 steps

1Step 1: Initialize a list to store all permutations.
2Step 2: Use a recursive function to explore each character in the string.
3Step 3: For each character, if it's a letter, branch into two recursive calls: one with the lowercase and one with the uppercase version.
4Step 4: If it's a digit, simply continue to the next character without changing it.
5Step 5: When reaching the end of the string, add the current permutation to the list.

solution.py19 lines

1def letterCasePermutation(s):
2    res = []
3    def backtrack(path, index):
4        if index == len(s):
5            res.append(''.join(path))
6            return
7        if s[index].isalpha():
8            path.append(s[index].lower())
9            backtrack(path, index + 1)
10            path.pop()
11            path.append(s[index].upper())
12            backtrack(path, index + 1)
13            path.pop()
14        else:
15            path.append(s[index])
16            backtrack(path, index + 1)
17            path.pop()
18    backtrack([], 0)
19    return res

ℹ

Complexity note: The time complexity is O(n²) because for each character, we might create two branches in the recursion tree, leading to 2^n combinations, and each combination takes O(n) time to build.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.