Check if two strings share the same pattern of repeated characters

Question

Is there an efficient Regex to assert that two string share the same pattern of repeated characters.

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

Event if it's not through Regex, I'm looking for the most efficient way to perform the task

Answer 1

The easiest way is probably to walk through both strings manually at the same time and build up a dictionary (that matces corresponding characters) while you are doing it:

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;

In the same manner you could construct a regex. This is certainly not more efficient for a single comparison, but it might be useful if you want to check one repetition pattern against multiple strings in the future. This time we associate characters with their back-references.

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 += "$";

For matter it will generate this regex: ^(.)(.)(.)\3(.)(.)$. For acquaintance this one: ^(.)(.)(.)(.)\1(.)(.)(.)\1\6\2(.)$. If could of course optimize this regular expression a bit afterwards (e.g. for the second one ^(.)(.)..\1.(.).\1\3\2$), but in any case, this would give you a reusable regex that checks against this one specific repetition pattern.

EDIT: Note that the given regex solution has a caveat. It allows mapping of multiple characters in the input string onto a single character in the test strings (which would contradict your last example). To get a correct regex solution, you would have to go a step further to disallow characters already matched. So acquaintance would have to generate this awful regular expression:

^(.)(?!\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)(.)$

And I cannot think of an easier way, since you cannot use backreferences in (negated) character classes. So maybe, if you do want to assert this as well, regular expressions are not the best option in the end.

Disclaimer: I am not really a .NET guru, so this might not be the best practice in walking through arrays in building up a dictionary or string. But I hope you can use it as a starting point.

Answer 2

I don't know how to do it using a regex, but in code I would run through both strings one character at a time, comparing as I go and building a comparison list:

t = l
r = o
e = a
etc.

Prior to adding each comparison, I'd check to see if a character from the first string already existed in the list. If the corresponding character from the second string does not match the comparison list then the string patterns don't match.