检查两个字符串是否共享相同的重复字符模式

Question

是否有一个有效的正则表达式断言两个字符串共享相同的重复字符模式.

("tree", "loaa") => true
("matter", "essare") => false
("paper", "mime") => false
("acquaintance", "mlswmodqmdlp") => true
("tree", "aoaa") => false

事件,如果它不通过正则表达式,我正在寻找最有效的方式来执行任务

Answer 1

最简单的方法可能是同时手动遍历两个字符串,并在执行时构建一个字典(匹配相应的字符):

if(input1.Length != input2.Length)
    return false;
var characterMap = new Dictionary<char, char>();
for(int i = 0; i < input1.Length; i++)
{
    char char1 = input1[i];
    char char2 = input2[i];
    if(!characterMap.ContainsKey(char1))
    {
        if (characterMap.ContainsValue(char2))
            return false;
        characterMap[char1] = char2;
    }
    else
    {
        if(char2 != characterMap[char1])
            return false;
    }
}
return true;

以同样的方式构建正则表达式.对于单个比较来说,这当然不是更有效,但如果您想在将来针对多个字符串检查一个重复模式,它可能会很有用.这次我们将字符与其反向引用相关联.

var characterMap = new Dictionary<char, int>();
string regex = "^";
int nextBackreference = 1;
for(int i = 0; i < input.Length; i++)
{
    char character = input[i];
    if(!characterMap.ContainsKey(character))
    {
        regex += "(.)";
        characterMap[character] = nextBackreference;
        nextBackreference++;
    }
    else
    {
        regex += (@"\" + characterMap[character]);
    }
}
regex += "$";

因为matter它会生成这个正则表达式:^(.)(.)(.)\3(.)(.)$.对于acquaintance这个:^(.)(.)(.)(.)\1(.)(.)(.)\1\6\2(.)$.如果当然可以稍后优化这个正则表达式(例如,对于第二个^(.)(.)..\1.(.).\1\3\2$),但无论如何,这将给你一个可重用的正则表达式来检查这个特定的重复模式.

编辑:请注意,给定的正则表达式解决方案有一个警告.它允许将输入字符串中的多个字符映射到测试字符串中的单个字符(这与您的上一个示例相矛盾).要获得正确的正则表达式解决方案,您必须更进一步禁止已匹配的字符.所以acquaintance必须生成这个可怕的正则表达式:

^(.)(?!\1)(.)(?!\1|\2)(.)(?!\1|\2|\3)(.)\1(?!\1|\2|\3|\4)(.)(?!\1|\2|\3|\4|\5)(.)(?!\1|\2|\3|\4|\5|\6)(.)\1\6\2(?!\1|\2|\3|\4|\5|\6|\7)(.)$

我想不出更简单的方法,因为你不能在(否定的)字符类中使用反向引用.所以也许,如果你也想断言这一点,那么正则表达式最终不是最好的选择.

免责声明:我不是一个真正的.NET大师,所以这可能不是在构建字典或字符串时遍历数组的最佳实践.但我希望你能以此为出发点.