784-字母大小写全排列.md

题目描述

字母大小写全排列

题目简述

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

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

分类

中等 回溯

思路

思路1

/**
 * @param {string} s
 * @return {string[]}
 */
var letterCasePermutation = function(s) {
  let strTrace = ''
  const res = []
  function backTrack (index) {
    if (index === s.length) {
      res.push(strTrace)
      return
    }
    const char = s.slice(index, index + 1)
    if (char === judgeChar(char)) {
      strTrace += char
      backTrack(index + 1)
      strTrace = strTrace.slice(0, -1)
      return
    }
    strTrace += char
    backTrack(index + 1)
    strTrace = strTrace.slice(0, -1)
    
    strTrace += judgeChar(char)
    backTrack(index + 1)
    strTrace = strTrace.slice(0, -1)
  }
  backTrack(0)
  return res
};

function judgeChar (char) {
  const code = char.charCodeAt()
  let _char = char
  // 小写
  if ( code >= 97 && code <= 122 ) {
    _char = char.toUpperCase()
  } else if(code >= 65 && code <= 90) {
    _char = char.toLowerCase()
  }
  return _char
}

• 问题拆解
  • 这个题像一个二叉树问题，每个字符位置下有两种状态（大写或小写，还有非字母的情况，不用进行处理）。
  • 定义judgeChar对字符ascii码判断进行大小写的转换，非字母则不变。
  • 从字符的第一位开始，如果非字母直接设定该字符后，进入第二个字母；如果是字母，先设定该字符位置为当前字母，进入第二个字母，结束后删除该字符，使用大小写转换后的字符为当前字母，结束后再删除该字符。