[종만북] [8장 동적 계획법] 8.3장 와일드카드

Approach

*에 몇 글자가 대응하는지 여부가 가장 중요하다. 이 문제를 완전탐색을 통해서 해결할 수 있다.

 

완전탐색을 통해 해결할 수 있으나, 문자열의 길이가 100자리 이하라는 것을 감안할 때 비둘기집 원리를 이용하면 총 101 * 101 가지 이하만 계산해주면 된다는 것을 이해할 수 있다. (즉, 중복되는 계산이 무조건적으로 생기므로 메모이제이션을 활용하면 중복되는 계산을 줄일 수 있다.)

Code

1. $0(N^3)$로 푸는 풀이

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
string W;
string T;
int dp[101][101];

int memoization(int w, int t){
    int& ret = dp[w][t];
    if(ret != -1) return ret;
    while(w < W.size() && t < T.size() && (W[w] == T[t] || W[w] == '?')){
        w++;
        t++;
    }

    if(w == W.size()) return ret = (t == T.size());
    if(W[w] == '*'){
        for(int i = t; i <= T.size(); i++){
            if(memoization(w + 1, i)) return ret = 1;
        }
    }
    return ret = 0;
}

int main(void){
    int c;
    cin >> c;
    while(c--){    
        cin >> W;
        int n;
        cin >> n;
        vector<string> v;
        for(int i = 0; i < n; i++){
            memset(dp, -1, sizeof(dp));
            cin >> T;
            if(memoization(0, 0)) v.push_back(T);
        }
        sort(v.begin(), v.end());
        for(int i = 0; i < v.size(); i++){
            cout << v[i] << "\n";
        }
    }
    return 0;
}

2. $O(N^2)$로 푸는 풀이

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
string W;
string T;
int dp[101][101];

bool memoization(int w, int t){
    int& ret = dp[w][t];
    if(ret != -1) return ret;
    while(w < W.size() && t < T.size() && (W[w] == T[t] || W[w] == '?')){
        return ret = memoization(w + 1, t + 1);
    }
    if(w == W.size()) return (t == T.size());

    if(W[w] == '*'){
        if(memoization(w + 1, t) || (t < T.size() && memoization(w, t + 1))) return ret = true;
    }
    return ret = false;
}

int main(void){
    int c;
    cin >> c;
    while(c--){    
        cin >> W;
        int n;
        cin >> n;
        vector<string> v;
        for(int i = 0; i < n; i++){
            memset(dp, -1, sizeof(dp));
            cin >> T;
            if(memoization(0, 0)) v.push_back(T);
        }
        sort(v.begin(), v.end());
        for(int i = 0; i < v.size(); i++){
            cout << v[i] << "\n";
        }
    }
    return 0;
}