字母大小写全排列

TIPS

转自 蝉壳学院: 字母大小写全排列 (opens new window)

作者: 火火 (opens new window)

TIPS

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

示例:

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

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

输入: S = "12345"
输出: ["12345"]

注意:

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

解题思路: 获取所有字母的索引, 进行一次全排列

下面分享两种解题方式

1. 第一种完美利用正则匹配筛选, 代码很漂亮

   /**
    * @param {string} S
    * @returns {array}
   */
   function permutations(S) {
     const result = [S]; // 存放结果的数组，先将S作为其中一个结果放入
     const reg = /[A-z]/g; // 匹配大小写字母
     let i = reg.exec(S); // 匹配到的第一个元素，主要是获取字母的索引
     while (i) { // 只要没有匹配结束就一直循环
       result.forEach(val => { // 对结果集的每一个结果进行遍历(第一次循环遍历一个元素，第二次遍历两个...)
         if (/[a-z]/.test(val[i.index])) { // 如果是小写 => 转成大写
           result.push(val.slice(0, i.index) + val[i.index].toLocaleUpperCase() + val.slice(reg.lastIndex));
         } else { // 如果是大写 => 转成小写
           result.push(val.slice(0, i.index) + val[i.index].toLocaleLowerCase() + val.slice(reg.lastIndex));
         }
       })
       i = reg.exec(S);
     }
     return result;
   }
   

   TIPS

   RegExp.prototype.exec() (opens new window)

   参数

   str: 要匹配正则表达式的字符串。

   返回值

   • 如果匹配成功，exec() 方法返回一个数组（包含额外的属性 index 和 input ），并更新正则表达式对象的 lastIndex 属性。完全匹配成功的文本将作为返回数组的第一项，从第二项起，后续每项都对应正则表达式内捕获括号里匹配成功的文本。
   • 如果匹配失败，exec() 方法返回 null，并将 lastIndex 重置为 0 。

   所以在上面 i = reg.exec(S) 每执行一次都会匹配到一个字母，依次往后挪

2. 第二种比较容易理解, 所有可能性转换成二进制

   /**
    * @param {string} S
   * @returns {array}
   */
   function permutations(S) {
     const result = []; // 存放结果的数组
     const reg = /[A-z]/g; // 匹配大小写字母
     const idxs = []; // 索引
     let item = reg.exec(S); // 获取字母的索引
     while (item) {
       idxs.push(item.index);
       item = reg.exec(S);
     }
     let len = idxs.length; // 多少个字母
     // 每个字母有两种可能，n个就有2^n种
     for (let j = 0; j < Math.pow(2, len); j++) {
       // j 最大的时候 guide 出现quan 1 的情况 表示全部大写
       let guide = j.toString(2); // 二进制表示大小写，0小写 1大写 010 表示 idxs的第二个字母变大写
       // 每次组合时都会去判断 idxs 中所有的字符是不是需要转换
       for (let i = len - 1, k = guide.length - 1; i >= 0; i--, k--) {
         // 每次都从一个字母处分开，前面的 + 字母转换 + 后面的
         S = S.slice(0, idxs[i])
           + (k < 0 || guide[k] === '0' ? S[idxs[i]].toLocaleLowerCase() : S[idxs[i]].toLocaleUpperCase())
           + S.slice(idxs[i] + 1);
       }
       // 通过一次 idxs 的循环 最终覆盖形成的 S 是当前大小写组合的最终结果
       result.push(S);
     }
     return result;
   }