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 <iostream>
2#include <vector>
3
4void backtrack(std::string &s, int index, std::vector<std::string> &result) {
5 if (index == s.size()) {
6 result.push_back(s);
7 return;
8 }
9 backtrack(s, index + 1, result);
10 if (isalpha(s[index])) {
11 s[index] ^= 32; // Toggle case
12 backtrack(s, index + 1, result);
13 s[index] ^= 32; // Revert change
14 }
15}
16
17std::vector<std::string> letterCasePermutation(std::string s) {
18 std::vector<std::string> result;
19 backtrack(s, 0, result);
20 return result;
21}
22
23int main() {
24 std::string s = "a1b2";
25 auto permutations = letterCasePermutation(s);
26 for (const auto &perm : permutations) {
27 std::cout << perm << std::endl;
28 }
29 return 0;
30}
31This C++ solution uses a similar backtracking strategy as the C solution. It maintains a vector of strings to store the results. By toggling each letter's case, it explores and stores all possible permutations of the string.
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.