中等

问题描述

给定一个字符串 s，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。

返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。

示例 1：

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

示例 2:

输入: s = "3z4"
输出: ["3z4","3Z4"]

提示:

• 1 <= s.length <= 12
• s 由小写英文字母、大写英文字母和数字组成

广度优先搜索

遍历字符串，当遇到数字时跳过继续遍历，当遇到字母时，此时会有两种选择：

• 保持当前字母不变，此时无需任何操作。
• 转换大小写，此时需要将结果集中的历史数据遍历一次，将对应字母进行替换再放入结果集中。

/**
 * @param {string} s
 * @return {string[]}
 */
var letterCasePermutation = function (s) {
  const n = s.length
  const ans = [s]
  let i = 0
  while (i < n) {
    if (isNaN(+s[i])) {
      const len = ans.length
      for (let j = 0; j < len; j++) {
        if (s[i] === s[i].toLowerCase()) {
          ans.push(ans[j].substring(0, i) + s[i].toUpperCase() + ans[j].substring(i + 1))
        } else {
          ans.push(ans[j].substring(0, i) + s[i].toLowerCase() + ans[j].substring(i + 1))
        }
      }
    }
    i++
  }
  return ans
}

• 时间复杂度：$O(n \times n^2)$
• 空间复杂度：$O(n \times n^2)$