C++에서 가중 문자열에 모음이 포함된 트리의 노드 계산

노드의 가중치를 문자열로 포함하는 이진 트리가 제공됩니다. 목표는 문자열에 모음이 포함되도록 가중치를 갖는 노드의 수를 찾는 것입니다. weight가 'aer'이면 모음 'a'와 'a'가 있으므로 노드가 계산됩니다.

예를 들어

입력

값을 입력한 후 생성될 트리는 다음과 같습니다. -

출력

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[]를 초기화합니다.

• 벡터 edge_graph를 사용하여 나무를 만듭니다.

• 전역변수 모음을 취하여 0으로 초기화합니다.

• check(string check_it) 함수는 s 문자열을 취하고 check_it에 모음이 포함되어 있으면 true를 반환합니다.

• length =check_it.length()를 check_it의 문자 수로 사용합니다.

• for 루프를 사용하여 인덱스 i=0에서 i까지 check_it 트래버스

• 각 check_it[i]를 소문자로 변환하여 c에 저장합니다.

• c가 모음( 'a', 'e' 'i', 'o', 'u' ) 중 하나와 같으면 true를 반환하고 그렇지 않으면 false를 반환합니다.

• string_vowel(int node, int root) 함수는 트리의 노드와 루트 노드를 가져와서 가중치가 문자로 포함된 트리의 노드 수를 반환합니다.

• str =Node_Weight[노드]를 가져옵니다.

• check(str)이 true를 반환하면 모음을 증가시킵니다.

• for 루프를 사용하여 벡터 edge_graph[노드]에서 트리를 탐색합니다.

• 벡터의 다음 노드에 대해 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