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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <ctype.h>
4#include <string.h>
5
6void backtrack(char *s, int index, char **result, int *returnSize) {
7 if (index == strlen(s)) {
8 result[*returnSize] = strdup(s);
9 (*returnSize)++;
10 return;
11 }
12 backtrack(s, index + 1, result, returnSize);
13 if (isalpha(s[index])) {
14 s[index] ^= 32; // Toggle case
15 backtrack(s, index + 1, result, returnSize);
16 s[index] ^= 32; // Revert change
17 }
18}
19
20char **letterCasePermutation(char *s, int *returnSize) {
21 int maxSize = 1 << strlen(s);
22 char **result = (char **)malloc(maxSize * sizeof(char *));
23 *returnSize = 0;
24 backtrack(s, 0, result, returnSize);
25 return result;
26}
27
28int main() {
29 char s[] = "a1b2";
30 int returnSize;
31 char **permutations = letterCasePermutation(s, &returnSize);
32 for (int i = 0; i < returnSize; i++) {
33 printf("%s\n", permutations[i]);
34 free(permutations[i]);
35 }
36 free(permutations);
37 return 0;
38}
39The C solution employs a recursive backtracking method to explore each character's transformation possibilities. It toggles the case of letters using the XOR operation and makes recursive calls to explore each possibility. The program handles string duplication and manages a list of results dynamically.
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.