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

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(.)(.)$。 熟人这个:^(.)(.)(.)(.)\1(.)(.)(.)\1\6\2(.)$。当然，如果可以稍后优化此正则表达式(例如，对于第二个 ^(.)(..)..\1.(.).\1\3\2$)，但是在任何情况下，这都会给你一个可重复使用的正则表达式来检查这个特定的重复模式。

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

^(.)(?!\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 大师，因此这可能不是遍历数组以构建字典或字符串的最佳实践。但我希望您可以以此为起点。