是否有可能为任意字符串的字谜生成(紧凑)正则表达式？

Question

问题:用任何语言编写一个程序,给定一串字符,生成一个匹配输入字符串的任何anagram的正则表达式.对于大于某个长度N的所有正则表达式,正则表达式必须比列出由"|"分隔的所有可能的字谜的"强力"解决方案短,并且当输入字符串增长时,正则表达式的长度应"缓慢"增长(理想情况下为线性) ,但可能是n).

你可以做到吗？我试过了,但是我的尝试远未成功,我开始怀疑它是否可能.我问的唯一原因是我以为我在另一个网站上看到过一个解决方案,但是很多没有意义的谷歌搜索未能再次发现它.

Answer 1

我认为这个javascript代码将根据您的规范工作.正则表达式长度将随输入的长度线性增加.它生成一个正则表达式,使用正向前瞻来匹配输入字符串的字谜.正则表达式的前瞻部分确保测试输入字符串中存在所有字符而忽略它们的顺序,匹配部分确保测试输入字符串的长度与输入字符串的长度相同(为其构​​造正则表达式).

function anagramRegexGenerator(input) {
    var lookaheadPart = '';
    var matchingPart = '^';
    var positiveLookaheadPrefix='(?=';
    var positiveLookaheadSuffix=')';
    var inputCharacterFrequencyMap = {}
    for ( var i = 0; i< input.length; i++ )
    {
        if (!inputCharacterFrequencyMap[input[i]]) {
            inputCharacterFrequencyMap[input[i]] = 1
        } else {
            ++inputCharacterFrequencyMap[input[i]];
        }
    }
    for ( var j in inputCharacterFrequencyMap) {
        lookaheadPart += positiveLookaheadPrefix;
        for (var k = 0; k< inputCharacterFrequencyMap[j]; k++) {
            lookaheadPart += '.*';
            if (j == ' ') {
                lookaheadPart += '\\s';
            } else {
                lookaheadPart += j;
            }
            matchingPart += '.';
        }
        lookaheadPart += positiveLookaheadSuffix;
    }
    matchingPart += '$';
    return lookaheadPart + matchingPart;
}

样本输入和输出如下

anagramRegexGenerator('aaadaaccc')
//generates the following string.
"(?=.*a.*a.*a.*a.*a)(?=.*d)(?=.*c.*c.*c)^.........$"
anagramRegexGenerator('abcdef ghij'); 
//generates the following string.
"(?=.*a)(?=.*b)(?=.*c)(?=.*d)(?=.*e)(?=.*f)(?=.*\s)(?=.*g)(?=.*h)(?=.*i)(?
=.*j)^...........$" 
//test run returns true
/(?=.*a)(?=.*b)(?=.*c)(?=.*d)(?=.*e)(?=.*f)(?=.*\s)(?=.*g)(?=.*h)(?=.*i)(?
=.*j)^...........$/.test('acdbefghij ')
//or using the RegExp object
//this returns true
new RegExp(anagramRegexGenerator('abcdef ghij')).test('acdbefghij ') 
//this returns false
new RegExp(anagramRegexGenerator('abcdef ghij')).test('acdbefghijj')