Sponsored
Sponsored
In this approach, we use a backtracking algorithm to generate all possible letter case permutations for each character in the string. We iterate over each character and decide to either transform it (if it's a letter) or leave it unchanged. By following this approach, we can explore all possible combinations.
Time Complexity: O(2^n), where n is the number of letters in the string.
Space Complexity: O(2^n) for storing the results.
1var letterCasePermutation = function(s) {
2 const result = [];
3
4 const backtrack = (path, index) => {
5 if (index === s.length) {
6 result.push(path.join(''));
7 return;
8 }
9 backtrack(path, index + 1);
10 if (isNaN(s[index])) {
11 path[index] = path[index] === s[index] ? path[index].toUpperCase() : path[index].toLowerCase();
12 backtrack(path, index + 1);
13 path[index] = s[index]; // Revert change
14 }
15 };
16
17 backtrack([...s], 0);
18 return result;
19};
20
21const s = "a1b2";
22console.log(letterCasePermutation(s));
23The JavaScript solution follows a similar logic of backtracking. It explores permutations by changing letter cases within the recursive function and maintains a current path state for each recursion level. The results are printed after the complete exploration.
This approach utilizes bit manipulation to generate permutations. Each letter can be either in uppercase or lowercase, and we represent each possibility with bits. By iterating through all possible binary combinations (where a bit signifies changing the case of a letter), we construct the result directly.
Time Complexity: O(2^n), where n is the number of letters since we iterate over each possible set of transformations.
Space Complexity: O(2^n) for storage of permutations.
1var letterCasePermutation = function(S) {
This JavaScript solution uses bit manipulation to devise all transformations. It iterates through a binary mask indicating which characters should change case, and appends each result permutation to an array.