O(mn)time,and O(mn) space DP solution, 344ms(how to be more quick?any other solutions?)


  • 0
    H
    class Solution {
    public:
    bool isMatch(string s, string p) {
        if(s.size()==0) return p.size()==0||(p.size()==1&&p[0]=='*');
        if(p.size()==0) return false;
        bool **pp = new bool*[p.size()+1];
        for(int i = 0; i <= p.size(); i++){
            pp[i] = new bool[s.size()+1];
        }
        pp[0][0]=true; pp[1][0]=p[0]=='*';
        for(int i = 1; i <= s.size(); i++) pp[0][i] = false;
        for(int i = 2; i <= p.size(); i++) pp[i][0] = p[i-1]=='*'?pp[i-1][0]:false;
        for(int i = 0; i < p.size(); i++){
            for(int j = 0; j < s.size(); j++){
                if(p[i]==s[j]||p[i]=='?'){
                    pp[i+1][j+1] = pp[i][j];
                }
                else if(p[i]=='*'){
                    pp[i+1][j+1] = pp[i][j+1]|pp[i+1][j];
                }
                else pp[i+1][j+1] = false;
            }
        }
        return pp[p.size()][s.size()];
    }
    };

Log in to reply
 

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