Regular C++ solution 20ms without DP


  • 0
    Y
    class Solution {
    public:
        bool isMatch(string s, string p) {
            int i = 0, j = 0, star = -1, match = 0, m = s.size(), n = p.size();
            while (i < m) {
                if ((s[i] == p[j] || p[j] == '?') && j < n)
                    i++, j++;
                else if (j < n && p[j] == '*') {
                    star = j;
                    match = i;
                    j++;
                }
                else if (star != -1) {
                    j = star + 1;
                    match++;
                    i = match;
                }
                else 
                    return false;
            }
            while (j < n && p[j] == '*')
                j++;
            return j == n;
        }
    };
    

Log in to reply
 

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