Letter Case Permutation
- 3 min read
- LC-Medium
- Backtracking
3 years ago
Solution
-
At any point, you can make two choices:
- Leave current character unchanged, move to next index
- Switch case of current character, move to next index
-
But the core functionality is just the three DFS branches:
-
- If character is number, do nothing, add character to current permutation, traverse
-
- If character is alphabet, do nothing, add character to current permutation, traverse
-
- If character is alphabet, SWITCH CASE, add character to current permutation, traverse
-
-
This way, we capture all possible permutations
-
Assume that the time complexity for string concatenation is negligible (because we can replace with list concatenation, and list concatenation is just very messy)
-
The code below is also much cleaner as we no longer check for the casing of a letter
- It doesn't matter because we only need to do either uppercase or lowercase
- BUT, WE also want ALL PERMUTATIONS
- This means not changing the case of a character all
- This is great because converting a lower case character to a lower case character is the same and not changing anything at all
- Same applies for uppercase
- This means that instead of checking the case of a character before converting it, we can just directly do both since one of these 2 cases will be for including the character without doing any transformation
| Time | Space | Explanation |
|---|---|---|
O(2^n) | O(n) | Space is because of recursion call stack depth |
function isAlphabet(char) {
const alphabets = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
return alphabets.includes(char);
}
function letterCasePermutation(s: string): string[] {
const permutations: string[] = [];
function dfs(i: number, perm: string) {
if (i === s.length) {
permutations.push(perm);
return;
}
if (isAlphabet(s[i])) {
dfs(i + 1, perm + s[i].toLowerCase());
dfs(i + 1, perm + s[i].toUpperCase());
} else {
dfs(i + 1, perm + s[i]);
}
}
dfs(0, '');
return permutations;
};
Inefficient (but pretty (imo)) solution
Why inefficient?
Because it uses a set to store values to avoid duplicates Duplicates occur because there are similar DFS branches due to the solution below not checking if the current character is lowercase before "converting" it to lowercase, and vice versa for uppercase
enum CaseType {
LOWER = 'lower',
UPPER = 'upper',
NEITHER = 'neither'
}
function getCharCase(char: string): CaseType {
if (char >= 'a' && char <= 'z') {
return CaseType.LOWER;
} else if (char >= 'A' && char <= 'Z') {
return CaseType.UPPER;
} else {
return CaseType.NEITHER;
}
}
function permuteLetter(ch: string) {
switch (getCharCase(ch)) {
case CaseType.NEITHER:
return ch;
case CaseType.LOWER:
return ch.toUpperCase();
case CaseType.UPPER:
return ch.toLowerCase();
}
}
function letterCasePermutation(s: string): string[] {
const permutations = new Set();
function dfs(i: number, perm: string[]) {
if (i === s.length) {
permutations.add(perm.join(''));
return;
}
perm.push(permuteLetter(s[i]));
dfs(i + 1, perm);
perm.pop();
perm.push(s[i]);
dfs(i + 1, perm);
perm.pop();
}
dfs(0, []);
return Array.from(permutations) as string[];
};