Elegant C# backtracking solution - beats 93% submissions


  • 0
    N
    public class Solution {
        
        private Dictionary<char, string> pd = new Dictionary<char, string>();
        private HashSet<string> ipd = new HashSet<string>();
        
        public bool WordPatternMatch(string pattern, string str) {
            if(str.Length<pattern.Length) return false;
            if(string.IsNullOrEmpty(pattern) && string.IsNullOrEmpty(str)) return true;
            if(string.IsNullOrEmpty(pattern) || string.IsNullOrEmpty(str)) return false;
            
            string c;
            if(pd.TryGetValue(pattern[0], out c))
            {
                if(!str.StartsWith(c)) return false;
                if(pattern.Length == 1) return str.Length==c.Length;
                if(str.Length == c.Length) return pattern.Length == 1;
                
                return WordPatternMatch(pattern.Substring(1), str.Substring(c.Length));
            }
            
            for(int i=0;i<= str.Length - pattern.Length;++i)
            {
                c = str.Substring(0,i+1);
                if(ipd.Contains(c)) continue;
                pd.Add(pattern[0], c);
                ipd.Add(c);
                
                if(WordPatternMatch(pattern.Substring(1), str.Substring(c.Length)))
                {
                    return true;
                }
                
                pd.Remove(pattern[0]);
                ipd.Remove(c);
            }
            
            return false;
        }
    }
    

    Comments/feedback welcome!


Log in to reply
 

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