有没有一种高效的正则表达式可以断言两个字符串具有相同的重复字符模式?
("tree", "loaa") => true
("matter", "essare") => false
("paper", "mime") => false
("acquaintance", "mlswmodqmdlp") => true
("tree", "aoaa") => false
即使不使用正则表达式,我仍在寻找执行任务的最有效方式。
有没有一种高效的正则表达式可以断言两个字符串具有相同的重复字符模式?
("tree", "loaa") => true
("matter", "essare") => false
("paper", "mime") => false
("acquaintance", "mlswmodqmdlp") => true
("tree", "aoaa") => false
即使不使用正则表达式,我仍在寻找执行任务的最有效方式。
最简单的方法可能是手动同时遍历两个字符串,并在此过程中建立一个字典(将相应字符进行匹配):
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大师,因此在构建字典或字符串时遍历数组可能不是最佳实践。但我希望您可以将其用作起点。
编辑:已接受的代码现在是正确的。这个将作为一种替代方案而存在(在几乎任何意义上都不如原来的好)。
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)) );
}
因此,重点是构建一个规范形式,以便稍后进行比较。这并不特别聪明,但确实可以得出正确的结果。
只因为我喜欢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++));
}
我不知道如何使用正则表达式来做,但是在代码中,我会逐个字符地遍历两个字符串,一边比较一边构建一个比较列表:
t = l
r = o
e = a
etc.
我刚遇到了同样的问题,然后我写了一段 Python 代码来解决它。这段代码非常简单,不需要导入任何额外的模块。基本思路是将两个给定的字符串分别转换为一个新的模式字符串,利用 ASCII 字符和它们对应的数值之间的关系。最后比较这两个模式字符串。
def SamePattern(s1, s2):
i = j = 97
p1 = p2 = ""
for index1, l1 in enumerate(s1):
if l1 not in s1[0:index1]:
p1 += chr(i)
i += 1
else:
p1 += chr(97 + s1.index(l1))
for index2, l2 in enumerate(s2):
if l2 not in s2[0:index2]:
p2 += chr(j)
j += 1
else:
p2 += chr(97 + s2.index(l2))
if p1 == p2:
return True
else:
return False