Produce different output - Wrong Answer based on KMP


  • 0
    G

    The algorithm is absolutely linear time complexity.

    However, on case: {"b", "*?*?"}

    My local output: false

    Submitted output: true

    Expected output: false

    class Solution {
    public:
        int *next;
        
        void getNext(const char *p, int len) {
            int i=0, j=-1;
            next[0]=-1;
            while (i<len) {
                if (j==-1 || p[i]=='?' || p[j]=='?' || p[i]==p[j])
                    next[++i]=++j;
                else
                    j=next[j];
            }
        }
    
        bool isMatch(const char *s, const char *p) {
            next=new int[strlen(p)+5];
            while (*s && *p) {
                if (*p=='*')
                    break;
                if (*p=='?' || *s==*p)
                    p++, s++;
                else
                    return false;
            }
            const char *q;
            int w,i,j;
            while (*p) {
                while (*p=='*')
                    p++;
                if (!*p)
                    return true;
                for (q=p+1;*q && *q!='*'; q++);
                int len=q-p;
                getNext(p, len);
                i=j=0;
                bool found=false;
                while (*s) {
                    if (j==-1 || p[j]=='?' || p[j]==*s) {
                        s++, j++;
                        if (j>=len) {
                            found=true;
                            break;
                        }
                    } else
                        j=next[j];
                }
                if (found)
                    s+=len, p=q;
                else
                    return false;
            }
            return !*s;
        }
    };

Log in to reply
 

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