JavaScript 字符串字母大小写组合生成

近一个月, 博客的多说评论框总是被一个河北IP发的黄网钓鱼链接刷屏, 除我以外, 不少多说用户表示自己也遇到了同样的情况. 多说评论框的官方似乎处于一个无人管理的状态, 官方的讨论区在几个月前就已经被广告帖刷爆, 这个评论框服务就算明天停止服务都不会显得奇怪.

多说的 WordPress 群里有人把http的各种大小写组合形式(比如hTTp, hTtP...)都列入了多说的关键词黑名单, 以此防止垃圾评论, 我自己试了一下好像没有效果...可能这个功能就是个摆设吧.

不过这个大小写的组合形式倒是引起了我的兴趣, 虽然我知道发垃圾评论的程序生成的组合肯定是随机的, 但研究一下这些组合有多少种, 该怎么输出所有的组合还是挺有意思的.

我只能想出两种可以穷举出这些组合的方式, 一种是二叉树, 一种是二进制. 不过二叉树的算法我已经不会写了(也许是时候去刷LeetCode了...), 所以就用了二进制的方式.

因为大小写只有2种形式, 所以可以直接用二进制表示, 比如0101可以表示hTtP, 0 表示小写, 1表示大写. 为字符串生成一个数, 然后将这个数不断递减1, 把每次递减的结果都转换成二进制然后转换成字符串即可. 代码如下:

'use strict'

function gen(str) {  
    let result = []

    for (let i = 2 ** str.length; i--;) {
        let bin = i.toString(2)
        bin = Array.from('0'.repeat(str.length - bin.length) + bin)
        for (let i = str.length; i--;) {
            if (Number(bin[i])) {
                bin[i] = str[i].toUpperCase()
            } else {
                bin[i] = str[i].toLowerCase()
            }
        }
        result.push(bin.join(''))
    }

    return result
}

gen('http')  

输出结果:

["HTTP", "HTTp", "HTtP", "HTtp", "HtTP", "HtTp", "HttP", "Http", "hTTP", "hTTp", "hTtP", "hTtp", "htTP", "htTp", "httP", "http"]

这个函数有个缺陷, 就是对于字母以外的字符也会当作字母处理, 比如我们把参数改成"http://"就会出现重复的结果:

["HTTP://", "HTTP://", "HTTP://", "HTTP://", "HTTP://", "HTTP://", "HTTP://", "HTTP://", "HTTp://", "HTTp://", "HTTp://", "HTTp://", "HTTp://", "HTTp://", "HTTp://", "HTTp://", "HTtP://", "HTtP://", "HTtP://", "HTtP://", "HTtP://", "HTtP://", "HTtP://", "HTtP://", "HTtp://", "HTtp://", "HTtp://", "HTtp://", "HTtp://", "HTtp://", "HTtp://", "HTtp://", "HtTP://", "HtTP://", "HtTP://", "HtTP://", "HtTP://", "HtTP://", "HtTP://", "HtTP://", "HtTp://", "HtTp://", "HtTp://", "HtTp://", "HtTp://", "HtTp://", "HtTp://", "HtTp://", "HttP://", "HttP://", "HttP://", "HttP://", "HttP://", "HttP://", "HttP://", "HttP://", "Http://", "Http://", "Http://", "Http://", "Http://", "Http://", "Http://", "Http://", "hTTP://", "hTTP://", "hTTP://", "hTTP://", "hTTP://", "hTTP://", "hTTP://", "hTTP://", "hTTp://", "hTTp://", "hTTp://", "hTTp://", "hTTp://", "hTTp://", "hTTp://", "hTTp://", "hTtP://", "hTtP://", "hTtP://", "hTtP://", "hTtP://", "hTtP://", "hTtP://", "hTtP://", "hTtp://", "hTtp://", "hTtp://", "hTtp://", "hTtp://", "hTtp://", "hTtp://", "hTtp://", "htTP://", "htTP://", "htTP://", "htTP://", "htTP://", "htTP://", "htTP://", "htTP://", "htTp://", "htTp://", "htTp://", "htTp://", "htTp://", "htTp://", "htTp://", "htTp://", "httP://", "httP://", "httP://", "httP://", "httP://", "httP://", "httP://", "httP://", "http://", "http://", "http://", "http://", "http://", "http://", "http://", "http://"]

有一种偷懒的处理方法, 就是直接对结果去重, 现在用 Set 去重还是很简单的: 把return result改成return Array.from(new Set(result))就可以了.

再运行一遍:

["HTTP://", "HTTp://", "HTtP://", "HTtp://", "HtTP://", "HtTp://", "HttP://", "Http://", "hTTP://", "hTTp://", "hTtP://", "hTtp://", "htTP://", "htTp://", "httP://", "http://"]

但是这种偷懒的方法并不能减少无谓的运算造成的时间损失, 对于二叉树而言, 跳掉非字母字符还是比较方便的, 对二进制来说就没那么容易了.

首先我们要分析字符串的组成:

str.split(/([a-zA-Z]+)/).filter(x => !!x)  

示例:

'ab12ab' => ["ab", "12", "ab"]  

统计:

str.split(/([a-zA-Z]+)/).filter(x => !!x).map(x => /^[a-zA-Z]+$/.test(x) ? [x.length, true] : [x.length, false])  

示例:

'ab12ab' => [[2, true], [2, false], [2, true]]  

现在我们知道字母的长度是 2 + 0 + 2 = 4, 非字母部分的索引在 [0 + 2, 0 + 2 + 2 - 1].

接下来让 gen 函数通过分析结果给 bin 补上非字母的字符就可以了:

'use strict'

function gen(str) {

    let guide = str.split(/([a-zA-Z]+)/).filter(x => !!x).map(x => /^[a-zA-Z]+$/.test(x) ? [x.length, true] : [x.length, false])
      , length = guide.reduce((result, current) => result + (current[1] ? current[0] : 0), 0)

    let result = []

    for (let i = 2 ** length; i--;) {
        let bin = i.toString(2)
        bin = Array.from('0'.repeat(length - bin.length) + bin)
        for (let i = 0; i < guide.length; i++) {
            if (!guide[i][1]) {
                let index = 0
                for (let j = 0; j < i; j++) {
                    index += guide[j][0]
                }
                bin.splice(index, 0, ...'0'.repeat(guide[i][0]).split(''))
            }
        }
        for (let i = str.length; i--;) {
            if (Number(bin[i])) {
                bin[i] = str[i].toUpperCase()
            } else {
                bin[i] = str[i].toLowerCase()
            }
        }
        result.push(bin.join(''))
    }

    return Array.from(new Set(result))
}

gen('http://')  

输出结果:

["HTTP://", "HTTp://", "HTtP://", "HTtp://", "HtTP://", "HtTp://", "HttP://", "Http://", "hTTP://", "hTTp://", "hTtP://", "hTtp://", "htTP://", "htTp://", "httP://", "http://"]

最后跑个分:

'use strict'

function gen1(str) {  
    let result = []

    for (let i = 2 ** str.length; i--;) {
        let bin = i.toString(2)
        bin = Array.from('0'.repeat(str.length - bin.length) + bin)
        for (let i = str.length; i--;) {
            if (Number(bin[i])) {
                bin[i] = str[i].toUpperCase()
            } else {
                bin[i] = str[i].toLowerCase()
            }
        }
        result.push(bin.join(''))
    }

    return Array.from(new Set(result))
}

function gen2(str) {  
    let guide = str.split(/([a-zA-Z]+)/).filter(x => !!x).map(x => /^[a-zA-Z]+$/.test(x) ? [x.length, true] : [x.length, false])
      , length = guide.reduce((result, current) => result + (current[1] ? current[0] : 0), 0)

    let result = []

    for (let i = 2 ** length; i--;) {
        let bin = i.toString(2)
        bin = Array.from('0'.repeat(length - bin.length) + bin)
        for (let i = 0; i < guide.length; i++) {
            if (!guide[i][1]) {
                let index = 0
                for (let j = 0; j < i; j++) {
                    index += guide[j][0]
                }
                bin.splice(index, 0, ...'0'.repeat(guide[i][0]).split(''))
            }
        }
        for (let i = str.length; i--;) {
            if (Number(bin[i])) {
                bin[i] = str[i].toUpperCase()
            } else {
                bin[i] = str[i].toLowerCase()
            }
        }
        result.push(bin.join(''))
    }

    return result
}

console.time('gen1')  
let result1 = gen1('http://123.com')  
console.timeEnd('gen1')

console.time('gen2')  
let result2 = gen2('http://123.com')  
console.timeEnd('gen2')

console.log(result1.length === result2.length)

let compareResult = []

for (let i = result1.length; i--;) {  
    compareResult.push(result1[i] === result2[i])
}

console.log(compareResult.every(x => x))  

输出结果:

gen1: 234.905ms  
gen2: 6.839ms  
true  
true