Intuition

'*'가 등장할 때마다 이를 분기로 삼고 재귀를 호출하는 방식으로 진행하면 되겠다고 생각했다.
그리고 이렇게 가능성 있는 케이스를 모두 살펴보고 한번이라도 가능한 케이스가 발견되면 true를 반환하면 될 것이라고 생각했다.

Approach

문자열 s와p 둘 중 하나라도 끝날때까지 문자열을 순회한다.
이때, 두 문자가 같지 않은 경우는 따로 처리를 해줘야한다. 그러나, 패턴이 '?'라면 넘어가줘도 된다.

int check(char* s, char* p, int sIdx, int pIdx){
    for (;s[sIdx]!=0&&p[pIdx]!=0;sIdx++,pIdx++){
        if (s[sIdx]!=p[pIdx]&&p[pIdx]!='?'){ // 두 문자가 '?'도 아니면서 일치하지 않을 경우
            ...
        }
    }
}

두 문자가 일치하지 않지만 true의 가능성을 갖기 위해서는 패턴이 asterisk여야 한다.
그런데 이때, asterisk가 연속으로 존재할 경우는 asterisk가 하나 있는 것과 다름이 없으므로 다른 문자가 나올때까지 패턴인덱스를 넘겨준다.
그런데 이렇게 넘겼는데 문자열이 끝나면, 마지막에 asterisk가 있으므로(이전까지의 과정에서 문제가 없었고) source문자열에 무엇이 있든간에 상관이 없다. (ex. abcd / a*)

int check(char* s, char* p, int sIdx, int pIdx){
    for (;s[sIdx]!=0&&p[pIdx]!=0;sIdx++,pIdx++){
        if (s[sIdx]!=p[pIdx]&&p[pIdx]!='?'){
            if (p[pIdx]=='*'){
                while (p[++pIdx]=='*') {} // 연속된 asterisk pass
                if (p[pIdx]==0) return 1; // 문자열이 끝난 경우
                ...
            }
            else return 0;
        }
    }
}

pIdx가 asterisk의 다음문자를 가리키고 있는 상황에서 sIdx 또한 pIdx의 문자와 동일한 문자가 나오는 케이스들을 모두 true의 가능성이 있는 경우로 볼 수 있다.
물론, asterisk의 다음문자가 '?'라면 sIdx에 어떤 문자가 오든 상관이 없다.

int check(char* s, char* p, int sIdx, int pIdx){
    for (;s[sIdx]!=0&&p[pIdx]!=0;sIdx++,pIdx++){
        if (s[sIdx]!=p[pIdx]&&p[pIdx]!='?'){
            if (p[pIdx]=='*'){
                while (p[++pIdx]=='*') {}
                if (p[pIdx]==0) return 1;
                for (;s[sIdx]!=0;sIdx++){ // 모든 케이스를 보기 위한 반복문
                    if (s[sIdx]==p[pIdx]||p[pIdx]=='?'){ 
                        if (check(s, p, sIdx+1, pIdx+1)) return 1; // 한 번이라도 가능한 케이스가 발생하면 바로 1을 반환하며 함수를 종료
                    } 
                }
                return 0; // 위의 for문을 마치고 이 line까지 왔다는 것은 asterisk와 매치되는 문자열이 존재하지 않는다는 뜻
            }
            else return 0;
        }
    }
}

위의 가장 큰 for문이 끝나게 되면, 두 문자열을 어디까지 순회하였는지 체크해야한다.
두 문자열 모두 끝까지 확인했다면, 특별히 문제가 없는 경우가 될 것이다.
그렇지 않다면 둘 중에 하나만 끝난경우로 두 문자열이 매치되지 않는 경우이다.
그러나, 마지막에 asterisk가 남아있는 경우는 예외이다. 이 경우 asterisk는 empty sequence와 매치되기 때문이다.

int check(char* s, char* p, int sIdx, int pIdx){
    for (;s[sIdx]!=0&&p[pIdx]!=0;sIdx++,pIdx++){
        if (s[sIdx]!=p[pIdx]&&p[pIdx]!='?'){
            if (p[pIdx]=='*'){
                while (p[++pIdx]=='*') {}
                if (p[pIdx]==0) return 1;
                for (;s[sIdx]!=0;sIdx++){ 
                    if (s[sIdx]==p[pIdx]||p[pIdx]=='?'){ 
                        if (check(s, p, sIdx+1, pIdx+1)) return 1; 
                    } 
                }
                return 0; 
            }
            else return 0;
        }
    }
}
if (s[sIdx]==0&&p[pIdx]==0) return 1;
else if (s[sIdx]==0) {
    while (p[pIdx]!=0) if (p[pIdx++]!='*') return 0; // asterisk외의 문자가 있는 경우 false
    return 1;
} 
else return 0;

여기까지 하게되면 기본적인 알고리즘은 완성된다. 그러나, 이상태로 submit하게되면 'Time Limit Exceeded'메세지가 뜨며 통과가 되지 않는다. 최적화를 위해 memoization을 적용해준다.

Solution

int memo[2000][2000];

int check(char* s, char* p, int sIdx, int pIdx){
    for (;s[sIdx]!=0&&p[pIdx]!=0;sIdx++,pIdx++){
        if (s[sIdx]!=p[pIdx]&&p[pIdx]!='?'){
            if (p[pIdx]=='*'){
                while (p[++pIdx]=='*') {}

                if (p[pIdx]==0) return 1;

                for (;s[sIdx]!=0;sIdx++){
                    if (s[sIdx]==p[pIdx]||p[pIdx]=='?'){ 
                        if(memo[sIdx+1][pIdx+1]==1) return memo[sIdx+1][pIdx+1]; 
// memo에 0이 적혀있더라도, for문에서 모든 가능성을 체크해야하므로 값을 return해서는 안된다.
                        if (memo[sIdx+1][pIdx+1]==-1){
                            if (memo[sIdx+1][pIdx+1] = check(s, p, sIdx+1, pIdx+1)) return 1;
                        }
                    } 
                }
                
                return 0;
            }

            else return 0;
        }
    }

    if (s[sIdx]==0&&p[pIdx]==0) return 1;
    else if (s[sIdx]==0) {
        while (p[pIdx]!=0) if (p[pIdx++]!='*') return 0;
        return 1;
    } 
    else return 0;
}

bool isMatch(char* s, char* p) {
    int slen;
    int plen;
    slen = plen = 0;

    while(s[slen]) slen++;
    while(p[plen]) plen++;

/*
memo[sIdx'+1'][pIdx'+1']까지 사용하므로 slen-1이 아니라 slen까지 memo를 초기화시켜줘야한다.
또한, 최대 범위가 2000이므로 slen과 plen을 상수로 처리한다고 생각할 수도 있는데, 그 경우에는 매번 4백만번의 반복문이 실행되고 여기에 1000개의 테스트케이스를 실행하게되면 엄청난 시간이 걸리게된다. 
memset함수의 경우 상수로 초기화해도 통과되는데, 이에 대해서는 추후에 다뤄보도록 하겠다.
*/
    for(int i = 0; i <= slen; i++) { 
        for(int j = 0; j <= plen; j++) memo[i][j] = -1;
    }

    return check(s,p,0,0);
}

지적 및 질문 환영