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.
1import java.util.ArrayList;
2import java.util.List;
3
4public class Solution {
5
6 public void backtrack(char[] s, int index, List<String> result) {
7 if (index == s.length) {
8 result.add(new String(s));
9 return;
10 }
11 backtrack(s, index + 1, result);
12 if (Character.isLetter(s[index])) {
13 s[index] ^= 32; // Toggle case
14 backtrack(s, index + 1, result);
15 s[index] ^= 32; // Revert change
16 }
17 }
18
19 public List<String> letterCasePermutation(String S) {
20 List<String> result = new ArrayList<>();
21 backtrack(S.toCharArray(), 0, result);
22 return result;
23 }
24
25 public static void main(String[] args) {
26 String s = "a1b2";
27 Solution solution = new Solution();
28 List<String> permutations = solution.letterCasePermutation(s);
29 for (String perm : permutations) {
30 System.out.println(perm);
31 }
32 }
33}
34This Java solution applies the backtracking approach using character arrays to toggle the case of letters in the input string. It stores permutations in an ArrayList which is returned after all possibilities are explored.
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.