C++で文字列の重みに母音を含む木のノード数をカウントする方法

各ノードの重みが文字列として与えられた二分木があるとします。この記事の目的は、重みの文字列に母音が含まれているノードの数を求めることです。たとえば、あるノードの重みが「aer」であれば、母音「a」と「e」が含まれているため、このノードはカウント対象になります。

入力例1

値を入力した後に作成される木は以下の通りです。

出力

Count the nodes of the tree whose weighted string contains a vowel are: 5

説明

木の各ノードと、それらに関連付けられた文字列の重みが与えられています。ここで、各ノードの文字列に母音が含まれているかどうかを確認します。

入力例2

値を入力した後に作成される木は以下の通りです。

出力

Count the nodes of the tree whose weighted string contains a vowel are: 3

説明

木の各ノードと、それらに関連付けられた文字列の重みをもとに、各ノードの文字列に母音が含まれているかどうかを確認します。

プログラムで使用するアプローチ

このアプローチでは、木を走査するためにDFS（深さ優先探索）を適用し、各ノードの重みの文字列に母音が含まれているかどうかをチェックします。このために、Node_Weight(100)とedge_graph[100]という2つのvectorを用意します。

• Node_Weight[]を各ノードの重みで初期化します。

• vector edge_graphを使って木（グラフ）を構築します。

• グローバル変数vowelを宣言し、0で初期化します。

• 関数check(string check_it)は文字列を受け取り、check_itに母音が含まれていればtrueを返します。

• length = check_it.length()として、check_itの文字数を取得します。

• forループでインデックスi=0からi<lengthまでcheck_itを走査します。

• 各check_it[i]を小文字に変換してcに格納します。

• cが母音（'a'、'e'、'i'、'o'、'u'）のいずれかと一致すればtrueを返し、最後まで一致しなければfalseを返します。

• 関数string_vowel(int node, int root)はノードと木のルートノードを受け取り、重みに母音が含まれるノードの数を返します。

• str = Node_Weight[node]として、現在のノードの重みを取得します。

• check(str)がtrueを返す場合はvowelをインクリメントします。

• forループでvector edge_graph[node]に基づいて木を走査します。

• vector内の次のノードに対してstring_vowel(it, node)を再帰的に呼び出します。

• すべての処理が完了すると、vowelには母音を含む重みを持つノードの総数が格納されます。

コード例

#include <bits/stdc++.h>
using namespace std;
vector<string> Node_Weight(100);
vector<int> edge_graph[100];
int vowel = 0;
bool check(string check_it){
    int length = check_it.length();
    for(int i = 0; i <length; i++){
        char c = tolower(check_it[i]);
        if(c == 'a' ||c == 'e' ||c == 'i' ||c == 'o' ||c == 'u'){
            return true;
        }
    }
    return false;
}
void string_vowel(int node, int root){
    string str = Node_Weight[node];
    if(check(str)){
        vowel++;
    }
    for (int it : edge_graph[node]){
        if(it == root){
            continue;
        }
        string_vowel(it, node);
    }
}
int main(){
    //ノードの重み
    Node_Weight[2] = "ae";
    Node_Weight[1] = "bcd";
    Node_Weight[4] = "io";
    Node_Weight[3] = "gfe";
    Node_Weight[8] = "tptpa";
    Node_Weight[9] = "iou";
    //グラフの辺を作成
    edge_graph[2].push_back(1);
    edge_graph[2].push_back(4);
    edge_graph[4].push_back(3);
    edge_graph[4].push_back(8);
    edge_graph[8].push_back(9);
    string_vowel(2, 2);
    cout<<"Count the nodes of the tree whose weighted string contains a vowel are: "<<vowel;
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

Count the nodes of the tree whose weighted string contains a vowel are: 5