子母大小全排列【LC784】
给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
比起dfs更容易想到回溯-.-
希望今天可以把数组整理完ya
回溯
- 思路：回溯遍历整个字符串，如果当前字符是数组，那么添加至sb末尾；如果当前字符是字母，那么将大小写的情分别添加至下一个字符。
- 实现：
。回溯三部曲
- 回溯函数模板返回值以及参数
- s（字符串）
- 全局变量：sb(存放符合条件单一结果)，res(存放符合条件结果的集合)
- 回溯函数终止条件
- 当sb的大小等于s的长度时终止
- 回溯搜索的遍历过程
- 判断是字母还是数组，如果是数组那么直接添加至sb末尾；如果是字母，那么将大小写字母分别添加至sb末尾
- 代码
class Solution { List<String> res = new ArrayList<>(); StringBuilder sb = new StringBuilder(); public List<String> letterCasePermutation(String s) { backtracking(s,0); return res; } public void backtracking(String s, int index){ if (index == s.length()){ res.add(new String(sb)); return; } char c = s.charAt(index); if (c >= '0' && c <= '9'){ sb.append(c); backtracking(s,++index); sb.deleteCharAt(sb.length()-1); index--; }else{// 字母 // 转化为大写 sb.append(Character.toUpperCase(c)); backtracking(s,index+1); sb.deleteCharAt(sb.length()-1); //index--; //转化为小写 sb.append(Character.toLowerCase(c)); backtracking(s,++index);a sb.deleteCharAt(sb.length()-1); index--; } } }
。复杂度
- 时间复杂度：O ( n ∗ 2 n )
- 空间复杂度：O ( n ∗ 2 n )
- 每个字符的大小写形式刚好差了 32，因此在大小写转化时可以用 c⊕32来进行转换和恢复。
c ^= 32;
dfs
当 s[idx]不为字母，将其直接追加到 cur 上，并决策下一个位置 idx+1；而当 s[idx为字母时，我们可以选择将 s[idx]追加到 cur 上（保留原字母）或是将 s[idx]进行翻转后再追加到 cur 上（进行大小写转换）。
class Solution { char[] cs; List<String> ans = new ArrayList<>(); public List<String> letterCasePermutation(String s) { cs = s.toCharArray(); dfs(0, s.length(), new char[s.length()]); return ans; } void dfs(int idx, int n, char[] cur) { if (idx == n) { ans.add(String.valueOf(cur)); return ; } cur[idx] = cs[idx]; dfs(idx + 1, n, cur); if (Character.isLetter(cs[idx])) { cur[idx] = (char) (cs[idx] ^ 32); dfs(idx + 1, n, cur); } } } 作者：宫水三叶 链接：https://leetcode.cn/problems/letter-case-permutation/solutions/1935889/by-ac_oier-x7f0/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
