二进制位/双递归 实现大小写转换全排列

本文介绍了32异或运算大小写转换，二进制全排列，以及脑洞下递归树节点间信息交互之参数传递

题面

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

示例：

输入：S = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]

S 的长度不超过12。
S 仅由数字和字母组成。

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/letter-ca...

分析

• 序列每个字符位置不发生变换，只是字母大小有改变
• 字母大小写转换前后两个状态，可以用二进制数0与1表示
• 假定初始串 abca 表示为 0000二进制状态数，那么 0100则表示串 aBca
• 换而言之，可用二进制数 0 - 1111表示 abca 所有字母大小写转换全排列

大小写转换

• 查表可知字母a 97， A 65, 空格 32
• byte 实际是 uint 类型的别名，因此可进行运算

  func translate(b byte) byte {
    if b >= 'a' {
        return b - ' '
    }
    return  b + ' '
  }

  更进一步， 将大小写字母与 32 进行异或运算，如下

  a := uint(97)
  A := uint(65)
  fmt.Println(string(a),string(A),string(a^32),string(A^32),string(A^32^32))
  // 输出 a A A a A

位运算

func letterCasePermutation(S string) []string {
    N := len(S)
    rs := []string{S}

    // 字母转换后的状态表
    m := make(map[int]byte,0)
    // 提取字母大小写转化后的1值状态表
    for i:=0;i< N;i++ {
        if num := int(S[i] - '0'); num > 9 {
            m[i]= translate(S[i]) // 或 S[i]^32
        }
    }

    // 字母大小写转换全排列 产生的个数（如二进制数 0 至 111 产生2的3次幂全排列数）
    binary := int(math.Pow(2,float64(len(m))))

    for k:=1;k < binary;k++ {
        s := []byte(S)  // 维护大小写转换前状态
        for i,j:=N-1,k;i>=0;i-- {
            if v, ok := m[i];ok {
                if j % 2 != 0 { // 状态1转换大小，状态0不转
                    s[i] = v 
                }
                j>>=1  // 右移，以便下次获取低位值
                if j == 0 {
                    break  // 已至最高位跳出
                }
            }
        }
        rs = append(rs, string(s))
    }
    return rs
}

双递归

func letterCasePermutation(S string) []string {
    rs := []string{}
    var backtrace func(int, []byte)

    backtrace = func(cur int, s []byte){
        if cur == len(S) {
            rs = append(rs, string(s))
            return 
        }
        backtrace(cur+1,s)
        if s[cur] - '0' > 9 { // 为字母则进入分支转换
            s[cur] ^= 32 // 处于前一个子递归的回溯期
            backtrace(cur+1,s) // 
        }
    }

    backtrace(0, []byte(S))
    return rs
}

其它

• 奇怪的是，二者性能上并没有太多的差异
• 递归重点在于递归间交互。比如，已选择路径，涉及退出条件，解空间等信息，以参数传递或 返回值的形式在递归调用时进行交换。
• 递归树节点（同一递归体内）中有嵌套式单次递归父子调用，或多次递归平行调用。平行递归一份入参对应多个子递归，这时引用类型入参若在前一个子递归体内被改变，则下一个子递归入参被污染，因此需要在每次调用前后进行手动清理（示例未手动修复两次子递归，在于路径参数'a'^32^32 == 'a')。
• 在PHP递归，通常参用局部静态变量作递归内部全局持有人，但也架不住全局变量的使用。静态变量只初始化一次，是否存活作用范围于只止于当前单个源文件？而全局变量存在于整个项目期间？

本作品采用《CC 协议》，转载必须注明作者和本文链接