Share c++ solution


  • 0
    W
    class Solution {
    public:
        bool isMatch(const char *s, const char *p) {
            int i = -0x80000000;
            for ( ; *s; ) {
                if (*p == '?' || *s == *p) {
                    ++i, ++s, ++p;
                } else if (*p == '*') {
                    while (*p == '*') ++p;
                    if (!*p) return true;
                    i = 0;
                } else if (i >= 0) {
                    s -= i - 1;
                    p -= i;
                    i = 0;
                } else {
                    return false;
                }
            }
            while (*p == '*') ++p;
            return !*p;
        }
    };
    

    O(m*n) dp got TLE, fastest should be kmp withO(m+n)

    here is a O(m*n) one (got AC)

    reference : https://github.com/soulmachine/leetcode


Log in to reply
 

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