原题链接在这里：https://leetcode.com/problems/letter-case-permutation/
题目：
Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.
Examples: Input: S = "a1b2" Output: ["a1b2", "a1B2", "A1b2", "A1B2"] Input: S = "3z4" Output: ["3z4", "3Z4"] Input: S = "12345" Output: ["12345"]
Note:
S will be a string with length between 1 and 12.S will consist only of letters or digits.题解：
For each dfs level, state needs current index and current item.
When the index hits the end, add to res.
Time Complexity: O(exponential).
Space: O(S.lengt()).
AC Java:
1 class Solution { 2 public List<String> letterCasePermutation(String S) { 3 List<String> res = new ArrayList<>(); 4 caseDfs(S, 0, new StringBuilder(), res); 5 return res; 6 } 7 8 private void caseDfs(String s, int cur, StringBuilder sb, List<String> res){ 9 if(cur == s.length()){ 10 res.add(sb.toString()); 11 return; 12 } 13 14 char c = s.charAt(cur); 15 if(Character.isDigit(c)){ 16 sb.append(c); 17 caseDfs(s, cur+1, sb, res); 18 sb.deleteCharAt(sb.length()-1); 19 }else{ 20 sb.append(Character.toLowerCase(c)); 21 caseDfs(s, cur+1, sb, res); 22 sb.deleteCharAt(sb.length()-1); 23 24 sb.append(Character.toUpperCase(c)); 25 caseDfs(s, cur+1, sb, res); 26 sb.deleteCharAt(sb.length()-1); 27 } 28 } 29 }
类似Combinations.
LeetCode 784. Letter Case Permutation
原文：https://www.cnblogs.com/Dylan-Java-NYC/p/11510900.html