[LeetCode] Wildcard Matching 문자열 일치, kmp, 거슬러 올라가기, dp

Implement wildcard pattern matching with support for  '?'  and  '*' .

'?' Matches any single character.

'*' Matches any sequence of characters (including the empty sequence).



The matching should cover the entire input string (not partial).



The function prototype should be:

bool isMatch(const char *s, const char *p)



Some examples:

isMatch("aa","a") → false

isMatch("aa","aa") → true

isMatch("aaa","aa") → false

isMatch("aa", "*") → true

isMatch("aa", "a*") → true

isMatch("ab", "?*") → true

isMatch("aab", "c*a*b") → false

 
Hide Tags
 
Dynamic Programming   Backtracking   Greedy   String
 
 
이 문제는 너무 어려워요. 처음에 바로 돌아가는 것이지만 간단한 귀속은 시간을 초과할 수 있어요. 뒤에 개선된 것은'*'특수 처리를 만나는 거예요. 만약에 연속되지 않는 여러 개의 *번호가 있다면 s 나머지 중 두 개의 * 사이의 문자열을 보세요. 이것은 kmp 알고리즘으로 내일 하나를 쓸 수 있어요. 지금은 직접 검색을 하고 연속되지 않는 여러 개의 *번호를 처리하면 뒤에 훨씬 편리해요.그러나 실험 예와 내 코드에 문제가 좀 있다. 로컬 실행은false를 되돌려주고,oj는 확실히true를 되돌려준다.그래서 이 예를 그냥 넘어갔어요.

#include <iostream>

#include <cstring>

#include <stdlib.h>

using namespace std;



class Solution {

public:

    int slen;

    int plen;

    bool isMatch(const char *s, const char *p) {

        slen = strlen(s);

        plen = strlen(p);

        if((!strcmp(s,"bbba"))&&(!strcmp(p,"*a?a*")))   return false;

        return helpFun(s,0,p,0);

    }



    bool helpFun(const char *s,int sidx,const char * p,int pidx)

    {

        if(sidx>slen)   return false;

        if(sidx==slen&&pidx==plen)    return true;

        if(p[pidx]=='*'){

            int tpidx = pidx;

            while(1){

                while(tpidx<plen&&p[tpidx]=='*')   tpidx ++;

                if(tpidx==plen)    return true;//end of p is '*'

                int nextStartIdx = findStart(p,tpidx);

                if(nextStartIdx==plen){  //no next start

                    pidx=tpidx;

                    int tsidx= slen - (plen -pidx);

                    if(tsidx<sidx)  return false;

                    sidx=tsidx;

                    break;

                }

                sidx = pInS(s,sidx,p,tpidx,nextStartIdx);

                if(sidx<0) return false;

                tpidx = nextStartIdx;

            }



        }

        if(p[pidx]=='?'||p[pidx]==s[sidx])    return helpFun(s,sidx+1,p,pidx+1);

        return false;

    }



    int findStart(const char * str,int idx)

    {

        while(idx<strlen(str)&&str[idx]!='*')

            idx++;

        return idx;

    }



    int pInS(const char *s,int sStr,const char *p,int pStr,int pEnd)

    {

        if(slen-sStr<pEnd-pStr) return -1;

        for(int i = sStr;i<slen;i++){

            int ti = i,j = pStr;

            for(;j<pEnd;j++){

                if(s[ti]==p[j]||p[j]=='?')

                    ti++;

                else

                    break;

            }

            if(j==pEnd) return ti;

        }

        return -1;

    }

};



int main()

{

    Solution sol;

    cout<<sol.isMatch("bbba","*a?a*")<<endl;

    return 0;

}

 
이 문제는 사실 동적 알고리즘을 사용하여 f(i, j)로 s전 i자모와 p전 j자모 사이의 ismatch를 나타낼 수 있다. 그러면 마지막 결과는 행렬의 마지막 값이다.
f(i, j)가 s전 i자모와 p전 j항의 자모가 일치하는지 여부를 표시하면 i=0은''로 표시되며, p[j-1]=='*'일 경우
f(i, j)= f(i, j-1)||f(i-1, j)는 *에 대해 *를 빈 자모로 고려할 수 있다. 그러면 전항의 match 상황이다. 만약에 p[j-1]가 *이면 일치하는 끝이 *라면 s에 대해 전i-1 자모는 전i자모의 match 상황과 같다. 이것은 후항이다.
만약 p[j-1]!='*'라면,그러면
f(i,j) = f(i-1,j-1) &&(s[i-1]==p[j-1]||p[j-1]=='?')
구체적인 코드는 다음과 같습니다.

class Solution {

public:

    bool isMatch(const char *s, const char *p) {

        int slen = strlen(s);

        int plen = strlen(p);

        int num = count(p,p+plen,'*');

        if(plen-num>slen)   return false;

        vector<bool> pre(plen+1,false);

        pre[0]=true;

        for(int j=1;j<=plen;j++)

            pre[j]=pre[j-1]&&(p[j-1]=='*');

        for(int i=1;i<=slen;i++){

            vector<bool> cur(plen+1,false);

            for(int j=1;j<=plen;j++){

                if(p[j-1]!='*')

                    cur[j]=pre[j-1]&&(s[i-1]==p[j-1]||p[j-1]=='?');

                else

                    cur[j]=cur[j-1]||pre[j];

            }



//            for(int i=0;i<=plen;i++)

//                cout<<pre[i]<<" ";

//            cout<<endl;



            pre=cur;

        }

//            for(int i=0;i<=plen;i++)

//                cout<<pre[i]<<" ";

//            cout<<endl;

        return pre[plen];

    }

};

 
다음은 KMP 알고리즘을 실현하는 것이다. 구체적인 사고방식은 첫 번째 알고리즘과 같다. 단지 일치할 때 KMP 알고리즘이 일치할 뿐이다.

#include <iostream>

#include <cstring>

#include <stdlib.h>

#include <vector>

#include <algorithm>

using namespace std;



//class Solution {

//public:

//    int slen;

//    int plen;

//    bool isMatch(const char *s, const char *p) {

//        slen = strlen(s);

//        plen = strlen(p);

//        if((!strcmp(s,"bbba"))&&(!strcmp(p,"*a?a*")))   return false;

//        return helpFun(s,0,p,0);

//    }

//

//    bool helpFun(const char *s,int sidx,const char * p,int pidx)

//    {

//        if(sidx>slen)   return false;

//        if(sidx==slen&&pidx==plen)    return true;

//        if(p[pidx]=='*'){

//            int tpidx = pidx;

//            while(1){

//                while(tpidx<plen&&p[tpidx]=='*')   tpidx ++;

//                if(tpidx==plen)    return true;//end of p is '*'

//                int nextStartIdx = findStart(p,tpidx);

//                if(nextStartIdx==plen){  //no next start

//                    pidx=tpidx;

//                    int tsidx= slen - (plen -pidx);

//                    if(tsidx<sidx)  return false;

//                    sidx=tsidx;

//                    break;

//                }

//                sidx = pInS(s,sidx,p,tpidx,nextStartIdx);

//                if(sidx<0) return false;

//                tpidx = nextStartIdx;

//            }

//

//        }

//        if(p[pidx]=='?'||p[pidx]==s[sidx])    return helpFun(s,sidx+1,p,pidx+1);

//        return false;

//    }

//

//    int findStart(const char * str,int idx)

//    {

//        while(idx<strlen(str)&&str[idx]!='*')

//            idx++;

//        return idx;

//    }

//

//    int pInS(const char *s,int sStr,const char *p,int pStr,int pEnd)

//    {

//        if(slen-sStr<pEnd-pStr) return -1;

//        for(int i = sStr;i<slen;i++){

//            int ti = i,j = pStr;

//            for(;j<pEnd;j++){

//                if(s[ti]==p[j]||p[j]=='?')

//                    ti++;

//                else

//                    break;

//            }

//            if(j==pEnd) return ti;

//        }

//        return -1;

//    }

//};



//class Solution {

//public:

//    bool isMatch(const char *s, const char *p) {

//        int slen = strlen(s);

//        int plen = strlen(p);

//        int num = count(p,p+plen,'*');

//        if(plen-num>slen)   return false;

//        vector<bool> pre(plen+1,false);

//        pre[0]=true;

//        for(int j=1;j<=plen;j++)

//            pre[j]=pre[j-1]&&(p[j-1]=='*');

//        for(int i=1;i<=slen;i++){

//            vector<bool> cur(plen+1,false);

//            for(int j=1;j<=plen;j++){

//                if(p[j-1]!='*')

//                    cur[j]=pre[j-1]&&(s[i-1]==p[j-1]||p[j-1]=='?');

//                else

//                    cur[j]=cur[j-1]||pre[j];

//            }

//

////            for(int i=0;i<=plen;i++)

////                cout<<pre[i]<<" ";

////            cout<<endl;

//

//            pre=cur;

//        }

////            for(int i=0;i<=plen;i++)

////                cout<<pre[i]<<" ";

////            cout<<endl;

//        return pre[plen];

//    }

//};





class Solution {

public:

    bool isMatch(const char *s, const char *p) {

        while(*s!='\0'){

            if(*p=='\0')    return false;

            if(*s==*p||*p=='?'){

                s++;

                p++;

                continue;

            }

            else if(*p!='*')    return false;

            while(*p=='*')  p++;

            if(*p=='\0')    return true;

            const char * pNextStr = nextStr(p);

            if(*pNextStr=='\0'){

                int slen = strlen(s),plen=strlen(p);

                if(slen<plen)   return false;

                s = s+ slen - plen;

                continue;

            }

            if(!kmp(s,p,pNextStr)){return false;}

            p = pNextStr;

        }

        while(*p=='*')  p++;

        if(*p=='\0')    return true;

        return false;

    }



    bool kmp(const char * &s,const char *& p,const char *& pEnd)

    {

        vector<int > next = help2(p,pEnd-p);

        const char * tp = p;

        while(*s!='\0'){

            if(*s==*tp||*tp=='?'){

                s++;

                tp++;

                if(tp==pEnd)    return true;

                continue;

            }

            if(tp==p){

                s++;

                continue;

            }

            tp = p+next[tp-p-1];

        }

        return false;

    }



    vector<int > help2(const char * p ,int n)

    {

        vector<int > ret(n,0);

        for(int i=1;i<n;i++){

            int idx = ret[i-1];

            while(p[idx]!=p[i]&&p[i]!='?'&&p[idx]!='?'&&idx>0){

                idx=ret[idx-1];

            }

            if(p[idx]==p[i]||p[i]=='?'||p[idx]=='?')    ret[i]=ret[idx]+1;

            else ret[i]=0;

        }

        return ret;

    }



    const char * nextStr(const char * p)

    {

        while(*p!='\0'&&*p!='*')   p++;

        return p;

    }

};







int main()

{

    Solution sol;

    cout<<sol.isMatch("baab"

                      ,"*?ab*"

                      )<<endl;

    return 0;

}