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

Question

是否有一个有效的正则表达式来声明两个字符串共享相同的重复字符模式。

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

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

Answer 1

最简单的方法可能是通过两个字符串手动在同一时间走，并建立一个字典（即matces对应的字符），而你正在做它：

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专家，所以这可能不是构建字典或字符串时通过数组遍历数组的最佳实践。但我希望你可以用它作为出发点。

Answer 2

我不知道如何使用正则表达式来做到这一点，但在代码中，我会跑通过两个字符串一个字符时，和比较，我去建立一个比较清单：

t = l 
r = o 
e = a 
etc. 

之前将每个比较，我会检查是否从第一个字符串的字符在列表中已经存在。如果第二个字符串中的相应字符与比较列表不匹配，则字符串模式不匹配。

Answer 3

编辑：接受的代码现在是正确的。这个将会在这里作为替代品（在几乎任何意义上都不太好）。

private static List<int> FindIndices(string str, char c, int ind) 
    { 
     var retval = new List<int>(); 
     int last = ind, temp; 
     while (0 < (temp = str.IndexOf(c, last))) 
     { 
      retval.Add(temp); 
      last = temp + 1; 
     }   
     return retval; 
    } 

    public static int[] CanonicalForm(string s) 
    { 
     string table = String.Empty; 
     var res = new int[s.Length]; 
     int marker = 0; 
     int lastInd; 

     for(int i=0; i < s.Length-1; ++i) 
     { 
      if (table.Contains(s[i])) 
       continue; 

      table += s[i];    
      lastInd = i+1; 

      if (s.IndexOf(s[i], lastInd) > 0) 
       res[i] = ++marker; 
      else 
       continue; 

      foreach (var v in FindIndices(s, s[i], lastInd)) 
       res[v] = marker; 
     } 
     return res; 
    } 

和比较：

public static bool ComparePatterns(string s1, string s2) 
    { 
     return ((s1.Length == s2.Length) && CanonicalForm(s1).SequenceEqual(CanonicalForm(s2))); 
    } 

所以关键是要建立一个规范的形式，以后可以比较。这不是特别聪明，但确实给出了正确的结果。

Answer 4

只因为我爱LINQ：:)

void Main() 
{ 
    Console.WriteLine(Map("tree") == Map("loaa")); 
    Console.WriteLine(Map("matter") == Map("essare")); 
    Console.WriteLine(Map("paper") == Map("mime")); 
    Console.WriteLine(Map("acquaintance") == Map("mlswmodqmdlp")); 
    Console.WriteLine(Map("tree") == Map("aoaa")); 
} 

public string Map(string input) 
{ 
    var seen = new Dictionary<char,int>(); 
    var index = 0; 
    return string.Join(
     string.Empty, 
     input.Select(c =>seen.ContainsKey(c) ? seen[c] : seen[c] = index++)); 
}