[プログラマー9992][2020 kakakao]歌詞検索問題を解く

👓 問題の概要

🔑 問題を解く

🥽 ソースコードとソースコード分析

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct Trie {
    int data;
    Trie *node[26];
};

bool makeTree(string& word, Trie &node, int idx, bool mode); //if exist then true, else false
int findWord(string& word, Trie &node, int idx);
Trie head[10020];
Trie tail[10020];


vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;

    for (size_t i = 0; i < words.size(); i++)
    {
        int length = words[i].size();
        if (!makeTree(words[i], head[length], 0, true)) {
            head[length].data++;
        }
    }

    for (size_t i = 0; i < words.size(); i++)
    {
        int length = words[i].length();
        if (!makeTree(words[i], tail[length], length - 1, false)) {
            tail[length].data++;
        }
    }
    for (size_t i = 0; i < queries.size(); i++)
    {
        int length = queries[i].size();
        int count = 0;
        while (queries[i][count] == '?') count++;
        if (count == length) {
            answer.push_back(head[count].data);
        }
        else if (queries[i][0] == '?') {
            reverse(queries[i].begin(), queries[i].end());
            answer.push_back(findWord(queries[i], tail[length], 0));
        }
        else {
            answer.push_back(findWord(queries[i], head[length], 0));
        }
    }
    return answer;
}
bool makeTree(string& word, Trie& node, int idx, bool mode){
    //node[alphabet] = 자식
    if (mode && word.length() <= idx) return false;
    if (!mode && idx < 0) return false;
    if (node.node[word[idx] - 'a'] == NULL) {
        node.node[word[idx] - 'a'] = new Trie();
    }
    else if (mode && idx == word.length() - 1 && node.node[word[idx] - 'a'] != NULL) {
        return true;
    }
    else if (!mode && idx == 0 && node.node[word[idx] - 'a'] != NULL) {
        return true;
    }
    if (mode == true) {
        if (!makeTree(word, *node.node[word[idx] - 'a'], idx + 1, mode)) {
            node.node[word[idx] - 'a']->data++;
            return false;
        }
        else {
            return true;
        }
    }
    else {
        if (!makeTree(word, *node.node[word[idx] - 'a'], idx - 1, mode)) {
            node.node[word[idx] - 'a']->data++;
            return false;
        }
        else {
            return true;
        }
    }


    return false;
}
int findWord(string& word, Trie& node, int idx) {

    if (&node == NULL) {
        return 0;
    }
    if (node.node[word[idx] - 'a'] == NULL && idx == word.length() - 1) {
        return node.data;
    }
    else if (node.node[word[idx] - 'a'] == NULL && idx != word.length() - 1) {
        return 0;
    }
    if (word.length() == idx - 1) {
        return node.node[word[idx] - 'a']->data;
    }
    if (word[idx + 1] == '?') {
        return node.node[word[idx] - 'a']->data;
    }
    return findWord(word, *node.node[word[idx] - 'a'], idx + 1);
}

🔨 問題ポスト