นับโหนดที่น้ำหนักเป็นสตริงมีพยัญชนะ (Vowel) ใน C++

โจทย์: ให้ Binary Tree ที่โหนดมีน้ำหนักเป็นสตริง ต้องการนับโหนดที่สตริงมีพยัญชนะ (a,e,i,o,u) อย่างน้อย 1 ตัว

แนวคิด: DFS + ตรวจสอบสตริง

ใช้ DFS เดินต้นไม้ (แทนด้วย adjacency list) สำหรับแต่ละโหนด ตรวจสอบสตริงน้ำหนักว่ามีพยัญชนะหรือไม่

ฟังก์ชันตรวจสอบพยัญชนะ

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;
}

DFS นับโหนด

vector<string> Node_Weight(100);
vector<int> edge_graph[100];
int vowel = 0;

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);
    }
}

ตัวอย่างเต็ม

#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: " << vowel;
    return 0;
}

ผลลัพธ์

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

โหนดที่มีพยัญชนะ: 2(ae), 4(io), 3(gfe), 8(tptpa), 9(iou) = 5 โหนด