C# DP Solution O(s*p)


  • 0
    K
    public class Solution {
        public bool IsMatch(string s, string p) {
            bool[,] dp = new bool[s.Length + 1, p.Length + 1];
            dp[0,0] = true;
            
            for(int i = 1; i <= p.Length; ++i){
                if(p[i-1] == '*' && dp[0,i-2]){
                    dp[0,i] = true;
                }
            }
            
            for(int i = 1; i <= s.Length; ++i){
                for(int j = 1; j <= p.Length; ++j){
                    // Case where current str char matches pattern char
                    if(s[i - 1] == p[j - 1] || p[j - 1] == '.'){
                        dp[i,j] = dp[i-1,j-1]; 
                    }
                    
                    if(p[j - 1] == '*'){
                        // Assume current str char doesnt match * char (0 times)
                        dp[i,j] = dp[i,j - 2];
    
                        // Case where current str char matches * char (1 or n times)
                        if(s[i-1] == p[j-2] || p[j-2] == '.'){
                            dp[i,j] |= dp[i-1,j] || dp[i,j-1];
                        }
                    }
                }
            }
            
            return dp[s.Length, p.Length];
        }
    }
    

Log in to reply
 

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