C# backtracking


  • 1
    public class Solution {
            public bool WordPatternMatch(string pattern, string str)
            {
                Dictionary<char, string> mappings = new Dictionary<char, string>();
                HashSet<string> used = new HashSet<string>();
                bool isValid = GeneratePatterns(pattern, 0, str, 0, mappings, used);
                return isValid;
            }
    
            public bool GeneratePatterns(string pattern, int pi, string str, int si, Dictionary<char, string> mappings, HashSet<string> used)
            {
                bool existingMappingIsGood = true;
                while (pi < pattern.Length && si < str.Length && existingMappingIsGood) {
                    
                    if (!mappings.ContainsKey(pattern[pi]))
                    {
                        break;
                    }
                    
                    string curString = str.Substring(si);
                    if (curString.StartsWith(mappings[pattern[pi]]))
                    {
                        si += mappings[pattern[pi]].Length;
                        pi++;
                    }
                    else
                    {
                        existingMappingIsGood = false;
                    }
                }
                
                if (!existingMappingIsGood)
                {
                    return false;
                }
    
                if (pi == pattern.Length && si == str.Length)
                {
                    foreach (var m in mappings)
                    {
                        Console.WriteLine(m.Key + "=>" + m.Value);
                    }
    
                    return true;
                }
    
                // The next pattern to look for is pi and the string needs to start from si.
                if (pi < pattern.Length && si < str.Length)
                {
                    int patternsLeft = pattern.Length - pi - 1;
                    // There should be atleast patternLeft characters left to accomodate for the rest of the pattern.
                    for (int len = 1; len <= str.Length - si - patternsLeft; len++)
                    {
                        string testMapping = str.Substring(si, len);
                        if (!used.Contains(testMapping))
                        {
                            mappings[pattern[pi]] = testMapping;
                            used.Add(testMapping);
                            
                            bool isValid = GeneratePatterns(pattern, pi + 1, str, si + len, mappings, used);
                            if (isValid)
                            {
                                return true;
                            }
            
                            used.Remove(testMapping);
                            mappings.Remove(pattern[pi]);
                        }
                    }
                }
    
                return false;
            }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.