wildcard 문제

  • swon31
    swon31

    풀다가 안풀려서 책에 있는 알고리즘대로 고쳤는데 오답이 뜹니다
    어느 부분에서 틀린 건지 알 수가 없어 질문 남깁니다

    #include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    string wildcard;
    vector<string> word;
    bool cache[101][101];
    bool search(int num, int w, int s) {
        if (cache[w][s] != false) return cache[w][s];
        if (w < wildcard.size() && s < word[num].size() && (wildcard.at(w) == '?' || wildcard.at(w) == word[num].at(s))) {
            return cache[w][s] = search(num, w + 1, s + 1);
        }
        if (w == wildcard.size()) return cache[w][s] = (s == word[num].size());
        if (wildcard.at(w) == '*') {
            if (search(num, w + 1, s) || (s < word[num].size() && search(num, w, s + 1)))   return cache[w][s] = true;
        }
        return cache[w][s] = false;
    
    
    }
    
    int main(void) {
        int num;
        int wordnum;
    
        cin >> num; //반복 횟수
        for (int i = 0; i < num; i++) {
            cin >> wildcard;
            cin >> wordnum;
            word.clear();
            for (int j = 0; j < wordnum; j++) {
                string temp;
                cin >> temp;
                word.push_back(temp);
            }
            for (int j = 0; j < word.size(); j++){
                for (int i = 0; i < 100; i++) {
                    for (int j = 0; j < 100; j++) {
                        cache[i][j] = false;
                    }
                }
                if (!search(j, 0, 0)) word.erase(word.begin() + j);
            }
            sort(word.begin(), word.end());
            for (int j = 0; j < word.size(); j++) {
                cout << word[j] << endl;
            }
        }
    
        return 0;
    }
    

    8년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan

    책에 있는 알고리즘 대로 해도 틀리는 이유는 main()에 버그가 있기 때문입니다.

    단어를 삭제하는 부분에 문제가 있습니다.


    8년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.