784. 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"]

[暴力解法]：

时间分析：

空间分析：

［思维问题］：

不知道怎么写DFS中的回溯法：只知道先写退出条件，再写循环

［一句话思路］：

先都变成小写再说简单粗暴。不是不可以，调用java已有的函数行，可见函数很多

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

DFS的循环中，退出条件是return; 不要把添加结果理解成退出
一般是主函数返回，helper类型为void，注意一下
Character.toUpperCase(a[pos])的操作对象是Character抽象类，不是a[pos]本身，所以要赋值。不要搞错对象了。

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

corner case需要带入值来思考，不能一概而论 eg本题null- null

［复杂度］：Time complexity: O() Space complexity: O()

［英文数据结构或算法，为什么不用别的数据结构或算法］：

回溯法：先启动，然后进行一步，下一步后再返回

Character是char的包装类,就像Integer和int ，以及Long和long一样。

Character是char的包装类，注意它是一个类，提供了很多方法的。

包装类和基本类型可以自动转换,这是jdk1.5(5.0)的新特性,叫做自动封箱和自动解封

即：

例1：

char ch='a';

Character ch1=ch;//自动封箱

Character c=new Character(a);

char c1=c;//自动解封

Character 方法：

序号	方法与描述
1	isLetter() 是否是一个字母
2	isDigit() 是否是一个数字字符
3	isWhitespace() 是否是一个空格
4	isUpperCase() 是否是大写字母
5	isLowerCase() 是否是小写字母
6	toUpperCase() 指定字母的大写形式
7	toLowerCase() 指定字母的小写形式
8	toString() 返回字符的字符串形式，字符串的长度仅为1

［关键模板化代码］：

void helper (char[] a, int pos, List<String> res) {
        //break
        if (pos == a.length) {
            res.add(new String(a));
            return ;
        }
        //start
        helper(a, pos + 1, res);
        //backtracing
        if (Character.isLetter(a[pos])) {
            a[pos] = Character.toUpperCase(a[pos]);
            helper(a, pos + 1, res);
            a[pos] = Character.toLowerCase(a[pos]);
        }

退出-开始-回溯

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

class Solution {
    public List<String> letterCasePermutation(String S) {
        //corner case
        List<String> res = new ArrayList<String>();
        if (S == null) {
            return null;
        }
        //dfs
        char[] a = S.toLowerCase().toCharArray();
        helper(a, 0, res);
        return res;
    }
    
    void helper (char[] a, int pos, List<String> res) {
        //break
        if (pos == a.length) {
            res.add(new String(a));
            return ;
        }
        //start
        helper(a, pos + 1, res);
        //backtracing
        if (Character.isLetter(a[pos])) {
            a[pos] = Character.toUpperCase(a[pos]);
            helper(a, pos + 1, res);
            a[pos] = Character.toLowerCase(a[pos]);
        }
    }
}

View Code