Убедитесь, что две строки имеют один и тот же шаблон повторяющихся символов

Ответ 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$), но в любом случае это даст вам многоразовое регулярное выражение, которое проверяет этот единственный шаблон повторения.

EDIT: Обратите внимание, что данное задание регулярного выражения имеет оговорку. Он позволяет отображать несколько символов во входной строке на один символ в тестовых строках (что противоречило бы вашему последнему примеру). Чтобы получить правильное решение регулярных выражений, вам нужно сделать еще один шаг, чтобы запретить сопоставляемые символы. Поэтому 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)(.)$

И я не могу придумать более простой способ, так как вы не можете использовать обратные ссылки в (отрицательных) классах символов. Так что, возможно, если вы do хотите утверждать это, регулярные выражения не являются лучшим вариантом в конце.

Отказ от ответственности: я на самом деле не .NET-гуру, поэтому это может быть не самая лучшая практика при прохождении через массивы при создании словаря или строки. Но я надеюсь, что вы можете использовать его в качестве отправной точки.

Ответ 2

Я не знаю, как это сделать с помощью регулярного выражения, но в коде я бы пробежал обе строки по одному символу за раз, сравнивая, как я иду, и строю список сравнения:

t = l
r = o
e = a
etc.

Прежде чем добавлять каждое сравнение, я проверил бы, будет ли символ из первой строки уже существовать в списке. Если соответствующий символ из второй строки не соответствует списку сравнения, то шаблоны строк не совпадают.

Ответ 3

EDIT: Принятый код теперь верен. Этот будет задерживаться здесь как альтернатива (которая менее хороша практически в любом смысле).

    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)) );
    }

Итак, нужно построить каноническую форму, которую можно сравнить позже. Это не особенно умно, но дает правильные результаты.

Ответ 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++));
}