Bijective Mapping

This was an interesting backtracking problem from Leetcode: 

Word Pattern II - LeetCode

291. Word Pattern II

Medium

Given a pattern and a string s, return true if s matches the pattern.

A string s matches a pattern if there is some bijective mapping of single characters to strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.

 

Example 1:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

Example 2:

Input: pattern = "aaaa", s = "asdasdasdasd"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "asd"

Example 3:

Input: pattern = "abab", s = "asdasdasdasd"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "a"
'b' -> "sdasd"
Note that 'a' and 'b' cannot both map to "asd" since the mapping is a bijection.

Example 4:

Input: pattern = "aabb", s = "xyzabcxzyabc"
Output: false

 

Constraints:

• 1 <= pattern.length, s.length <= 20
• pattern and s consist of only lower-case English letters.

This is a backtracking problem but with the characteristic that there is a bijective mapping required. It then requires us to have two hash maps: one mapping the letter to a substring, and another one keeping track of the used substrings. Other than that, normal backtracking. Code is below, cheers, ACC.

public bool WordPatternMatch(string pattern, string s)
{
    Hashtable finalMap = new Hashtable();
    bool retVal = _WordPatternMatch(pattern, 0, s, 0, finalMap, new Hashtable());

    if (retVal)
    {
        Console.WriteLine("Solution found. Mapping:");
        foreach (char c in finalMap.Keys)
        {
            Console.WriteLine("{0} -> {1}", c, (string)finalMap[c]);
        }
    }
    else
    {
        Console.WriteLine("Did not find solution.");
    }

    return retVal;
}

private bool _WordPatternMatch(string pattern,
                                    int indexPattern,
                                    string s,
                                    int indexS,
                                    Hashtable patternMap,
                                    Hashtable mapsAlreadyUsed)
{
    //Base case
    if (indexPattern >= pattern.Length && indexS >= s.Length) return true;
    if (indexPattern >= pattern.Length || indexS >= s.Length) return false;

    //Induction case 1:
    //This takes place when the pattern for the first letter has already been added
    if (patternMap.ContainsKey(pattern[indexPattern]))
    {
        string mappedPattern = (string)patternMap[pattern[indexPattern]];
        if (!s.Substring(indexS).StartsWith(mappedPattern)) return false;
        return _WordPatternMatch(pattern, indexPattern + 1, s, indexS + mappedPattern.Length, patternMap, mapsAlreadyUsed);
    }
    else
    {
        //Induction case 2:
        //In this case, the first letter in the pattern has not been mapped
        //Code will then use backtrack to try all possible mappings
        string mappedPattern = "";
        for (int i = indexS; i < s.Length; i++)
        {
            mappedPattern += s[i].ToString();
            if (!mapsAlreadyUsed.ContainsKey(mappedPattern))
            {
                mapsAlreadyUsed.Add(mappedPattern, true);
                patternMap.Add(pattern[indexPattern], mappedPattern);
                if (_WordPatternMatch(pattern, indexPattern + 1, s, i + 1, patternMap, mapsAlreadyUsed)) return true;
                patternMap.Remove(pattern[indexPattern]);
                mapsAlreadyUsed.Remove(mappedPattern);
            }
        }
    }

    //The only valid return case should be in the base case
    //Hence at this point, return false
    return false;
}