Dado un árbol y los pesos (en forma de strings) de todos los Nodes, la tarea es contar los Nodes cuyos pesos contienen una vocal.
Ejemplos:
Aporte:
Salida: 2
Solo las strings de los Nodes 1 y 5 contienen vocales.
Enfoque: realice dfs en el árbol y para cada Node, verifique si su string contiene vocales, si es así, incremente el conteo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
int cnt = 0;
vector<int> graph[100];
vector<string> weight(100);
// Function that returns true
// if the string contains any vowel
bool containsVowel(string str)
{
for (int i = 0; i < str.length(); i++)
{
char ch = tolower(str[i]);
if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o'
|| ch == 'u')
return true;
}
return false;
}
// Function to perform dfs
void dfs(int node, int parent)
{
// Weight of the current node
string x = weight[node];
// If the weight contains any vowel
if (containsVowel(x))
cnt += 1;
for (int to : graph[node])
{
if (to == parent)
continue;
dfs(to, node);
}
}
// Driver code
int main()
{
// Weights of the node
weight[1] = "geek";
weight[2] = "btch";
weight[3] = "bcb";
weight[4] = "by";
weight[5] = "mon";
// Edges of the tree
graph[1].push_back(2);
graph[2].push_back(3);
graph[2].push_back(4);
graph[1].push_back(5);
// Function call
dfs(1, 1);
cout << cnt;
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG {
static int cnt = 0;
static Vector<Vector<Integer> > graph
= new Vector<Vector<Integer> >();
static Vector<String> weight = new Vector<String>();
// Function that returns true
// if the String contains any vowel
static boolean containsVowel(String str)
{
for (int i = 0; i < str.length(); i++)
{
char ch = str.charAt(i);
if (ch < 97)
ch += 32;
if (ch == 'a' || ch == 'e' || ch == 'i'
|| ch == 'o' || ch == 'u')
return true;
}
return false;
}
// Function to perform dfs
static void dfs(int node, int parent)
{
// Weight of the current node
String x = weight.get(node);
// If the weight contains any vowel
if (containsVowel(x))
cnt += 1;
for (int i = 0; i < graph.get(node).size(); i++)
{
if (graph.get(node).get(i) == parent)
continue;
dfs(graph.get(node).get(i), node);
}
}
// Driver code
public static void main(String args[])
{
// Weights of the node
weight.add("");
weight.add("geek");
weight.add("btch");
weight.add("bcb");
weight.add("by");
weight.add("mon");
for (int i = 0; i < 100; i++)
graph.add(new Vector<Integer>());
// Edges of the tree
graph.get(1).add(2);
graph.get(2).add(3);
graph.get(2).add(4);
graph.get(1).add(5);
// Function call
dfs(1, 1);
System.out.println(cnt);
}
}
// This code is contributed by andrew1234
Python3
# Python3 implementation of the approach cnt = 0 graph = [[] for i in range(100)] weight = [0 for i in range(100)] # Function that returns True # if the contains any vowel def containsVowel(Str): for i in range(len(Str)): ch = Str[i] if (ch == 'a' or ch == 'e' or ch == 'i' or ch == 'o' or ch == 'u'): return True return False # Function to perform dfs def dfs(node, parent): global cnt # Weight of the current node x = weight[node] # If the weight contains any vowel if (containsVowel(x)): cnt += 1 for to in graph[node]: if (to == parent): continue dfs(to, node) # Driver code # Weights of the node weight[1] = "geek" weight[2] = "btch" weight[3] = "bcb" weight[4] = "by" weight[5] = "mon" # Edges of the tree graph[1].append(2) graph[2].append(3) graph[2].append(4) graph[1].append(5) # Function call dfs(1, 1) print(cnt) # This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG {
static int cnt = 0;
static List<List<int> > graph = new List<List<int> >();
static List<String> weight = new List<String>();
// Function that returns true
// if the String contains any vowel
static Boolean containsVowel(String str)
{
for (int i = 0; i < str.Length; i++)
{
char ch = str[i];
if (ch < 97)
ch += (char)32;
if (ch == 'a' || ch == 'e' || ch == 'i'
|| ch == 'o' || ch == 'u')
return true;
}
return false;
}
// Function to perform dfs
static void dfs(int node, int parent)
{
// Weight of the current node
String x = weight[node];
// If the weight contains any vowel
if (containsVowel(x))
cnt += 1;
for (int i = 0; i < graph[node].Count; i++)
{
if (graph[node][i] == parent)
continue;
dfs(graph[node][i], node);
}
}
// Driver code
public static void Main(String[] args)
{
// Weights of the node
weight.Add("");
weight.Add("geek");
weight.Add("btch");
weight.Add("bcb");
weight.Add("by");
weight.Add("mon");
for (int i = 0; i < 100; i++)
graph.Add(new List<int>());
// Edges of the tree
graph[1].Add(2);
graph[2].Add(3);
graph[2].Add(4);
graph[1].Add(5);
// Function call
dfs(1, 1);
Console.WriteLine(cnt);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
let cnt = 0;
let graph = [];
let weight = [];
// Function that returns true
// if the String contains any vowel
function containsVowel(str)
{
for(let i = 0; i < str.length; i++)
{
let ch = str[i];
if (ch < 97)
ch += 32;
if (ch == 'a' || ch == 'e' || ch == 'i' ||
ch == 'o' || ch == 'u')
return true;
}
return false;
}
// Function to perform dfs
function dfs(node, parent)
{
// Weight of the current node
let x = weight[node];
// If the weight contains any vowel
if (containsVowel(x))
cnt += 1;
for(let i = 0; i < graph[node].length; i++)
{
if (graph[node][i] == parent)
continue;
dfs(graph[node][i], node);
}
}
// Driver code
// Weights of the node
weight.push("");
weight.push("geek");
weight.push("btch");
weight.push("bcb");
weight.push("by");
weight.push("mon");
for(let i = 0; i < 100; i++)
graph.push([]);
// Edges of the tree
graph[1].push(2);
graph[2].push(3);
graph[2].push(4);
graph[1].push(5);
// Function call
dfs(1, 1);
document.write(cnt);
// This code is contributed by patel2127
</script>
Producción
2
Análisis de Complejidad:
Complejidad de tiempo: O(N*Len) donde Len es la longitud máxima de la string ponderada de un Node en el árbol dado.
En DFS, cada Node del árbol se procesa una vez y, por lo tanto, la complejidad debida al DFS es O(N) para N Nodes en el árbol. Además, el procesamiento de cada Node implica atravesar la string ponderada de ese Node una vez, lo que agrega una complejidad de O (Len) donde Len es la longitud de la string ponderada. Por lo tanto, la complejidad temporal total es O(N*Len).
Espacio Auxiliar: O(1).
No se requiere ningún espacio adicional, por lo que la complejidad del espacio es constante.
Publicación traducida automáticamente
Artículo escrito por SURENDRA_GANGWAR y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA