Wildcard

문제

https://algospot.com/judge/problem/read/WILDCARD#

코드

#include <iostream>
#include <string>

using namespace std;

bool match(const string& w, const string& s) {
    int pos = 0;
    while (pos < w.size() && pos < s.size() && (w[pos] == '?' || w[pos] == s[pos]))
        pos++;
    if (pos == w.size())
        return w.size() == s.size();
    if (w[pos] == '*') {
        for (int skip = 0; pos + skip <= s.size(); skip++)
            if (match(w.substr(pos + 1), s.substr(pos + skip)))
                return true;
    }
    return false;

}

int cache[101][101];

string W, S;

int matchMemo(int w, int s) {
    int& ret = cache[w][s];
    if (ret != -1)
        return ret;

    while (w < W.size() && s < S.size() && (W[w] == '?' || W[w] == S[s])) {
        w++;
        s++;
    }
    if (w == W.size())
        return W.size() == S.size();
    if (W[w] == '*') {
        if(matchMemo(w+1,s) || (s  < S.size() && matchMemo(w, s+1)))
            return ret;

    }
    return ret = 0;
}

피드백

• 일단 못풀었다. 처음엔 뭔가 DP처럼 풀고싶어서 w의 첫번째 자리를 s의 몇 번째 자리부터 매칭시키는 걸 해봤는데 실패
• 책의 알고리즘은 다음과 같다.
  • 와일드패턴과 문자열이 서로 매칭될수 있을 때 까지 오프셋을 움직인다.
  • 멈췄을 때 와일드 패턴의 끝인지 판단한다.
  • 끝이라면 문자열도 끝인지 판단한다. 문자열도 끝이라면 정답이고, 그렇지 않다면 더 확인해야 한다.
  • 와일드패턴의 와일드 문자에 도달했는지 확인한다.
  • 그렇다면 문자열의 현재 문자를 와일드 문자에 먹일지, 와일드 문자 다음의 패턴으로 이을지 두 가지 경우에 대해 진행해야된다.
  • 둘중 하나라도 정답이 나오면 정답이기에, 위와 같이 코드를 짜서 ret에 반영시켜 리턴한다.
  • 위의 경우에 아무것도 해당되지 않는다면 그냥 문자가 틀린 것이다. 오답인 0을 리턴한다.
• 책의 풀이는 먼저 완전탐색으로 구현하고, 중복되는 케이스를 메모이제이션 한 풀이를 보였다.
  • 이 풀이는 완전탐색을 먼저 구현하고 중복이 될 수 있는 것을 찾으면 dp를 구현할 수 있기 때문에 꼭 생각해두자
  • 물론, 완전탐색 방법을 먼저 생각해야 한다... (이 문제는 생각을 못함)