นับโหนดของต้นไม้ที่สตริงที่มีน้ำหนักประกอบด้วยสระในภาษา C++

รับไบนารีทรีที่มีน้ำหนักของโหนดเป็นสตริง เป้าหมายคือการหาจำนวนโหนดที่มีน้ำหนักเพื่อให้สตริงมีสระ หากน้ำหนักเป็น 'aer' ก็จะมีสระ 'a' และ 'e' ดังนั้นโหนดจะถูกนับ

ตัวอย่าง

อินพุต

ต้นไม้ที่จะถูกสร้างขึ้นหลังจากป้อนค่าจะได้รับด้านล่าง -

ผลลัพธ์

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

คำอธิบาย

เราได้รับกับโหนดต้นไม้และน้ำหนักสตริงที่เกี่ยวข้องกับแต่ละโหนด ตอนนี้เราตรวจสอบว่าสตริงของโหนดมีสระหรือไม่

อินพุต

ต้นไม้ที่จะถูกสร้างขึ้นหลังจากป้อนค่าจะได้รับด้านล่าง -

ผลลัพธ์

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

คำอธิบาย

with the tree nodes and the string weights associated with each node. Now we check whether the string of nodes contains vowels or not.

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

ในแนวทางนี้ เราจะใช้ DFS บนกราฟของต้นไม้เพื่อสำรวจมัน และตรวจสอบว่าน้ำหนักของโหนดมีสตริงที่มีสระหรือไม่ ใช้เวกเตอร์ Node_Weight(100) และ edge_graph[100] สองตัวเพื่อการนี้

• เริ่มต้น Node_Weight[] ด้วยน้ำหนักของโหนด

• สร้างต้นไม้โดยใช้ vector edge_graph

• ใช้เสียงสระตัวแปรส่วนกลางและเริ่มต้นด้วย 0

• การตรวจสอบฟังก์ชัน (string check_it) รับ s สตริงและคืนค่า จริง หาก check_it มีสระอยู่ในนั้น

• ใช้ length =check_it.length() เป็นจำนวนอักขระใน check_it

• สำรวจ check_it โดยใช้ for loop จาก index i=0 ถึง i

• นำแต่ละ check_it[i] มาแปลงเป็นตัวพิมพ์เล็กและจัดเก็บไว้ใน c.

• ถ้า c เท่ากับสระตัวใดตัวหนึ่ง ( 'a', 'e' 'i', 'o', 'u' ) ให้คืนค่า true มิฉะนั้นจะคืนค่าเท็จ

• ฟังก์ชัน string_vowel(int node, int root) รับโหนดและโหนดรูทของต้นไม้และส่งคืนจำนวนโหนดในทรีที่กำหนดซึ่งมีน้ำหนักที่มีสระเป็นอักขระ

• ใช้ str =Node_Weight[node].

• ถ้า check(str) คืนค่าเป็น true ให้เพิ่มสระ

• ต้นไม้ขวางใน vector edge_graph[node] ใช้สำหรับวนซ้ำ

• เรียก 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(){
   //weight of the nodes
   Node_Weight[2] = "ae";
   Node_Weight[1] = "bcd";
   Node_Weight[4] = "io";
   Node_Weight[3] = "gfe";
   Node_Weight[8] = "tptpa";
   Node_Weight[9] = "iou";
   //create graph edge
   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