Cuente los Nodes del árbol que forman un pangrama cuando se concatenan con los Nodes del subárbol

Dado un árbol y los pesos (en forma de strings) de todos los Nodes, la tarea es contar los Nodes cuya string ponderada cuando se concatena con las strings de los Nodes del subárbol se convierte en un pangrama. 
Pangrama: Un pangrama es una oración que contiene todas las letras del alfabeto inglés.

Ejemplos: 
 

Aporte: 
 

Salida: 1 
Solo la string ponderada del subárbol del Node 1 forma el pangrama. 

Enfoque: Realice dfs en el árbol y actualice el peso de cada Node de modo que almacene su peso concatenado con los pesos de los Nodes del subárbol. Luego, cuente los Nodes cuya string ponderada actualizada forma un pangrama.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
vector<int> graph[100];
vector<string> weight(100);
 
// Function that returns if the
// string x is a pangram
bool Pangram(string x)
{
    map<char, int> mp;
    int n = x.size();
 
    for (int i = 0; i < n; i++)
        mp[x[i]]++;
    if (mp.size() == 26)
        return true;
    else
        return false;
}
 
// Function to return the count of nodes
// which make pangram with the
// sub-tree nodes
int countTotalPangram(int n)
{
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (Pangram(weight[i]))
            cnt++;
    return cnt;
}
 
// Function to perform dfs and update the nodes
// such that weight[i] will store the weight[i]
// concatenated with the weights of
// all the nodes in the sub-tree
void dfs(int node, int parent)
{
 
    for (int to : graph[node]) {
        if (to == parent)
            continue;
        dfs(to, node);
        weight[node] += weight[to];
    }
}
 
// Driver code
int main()
{
    int n = 6;
 
    // Weights of the nodes
    weight[1] = "abcde";
    weight[2] = "fghijkl";
    weight[3] = "abcdefg";
    weight[4] = "mnopqr";
    weight[5] = "stuvwxy";
    weight[6] = "zabcdef";
 
    // Edges of the tree
    graph[1].push_back(2);
    graph[2].push_back(3);
    graph[2].push_back(4);
    graph[1].push_back(5);
    graph[5].push_back(6);
 
    dfs(1, 1);
 
    cout << countTotalPangram(n);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG{
     
@SuppressWarnings("unchecked")
static Vector<Integer> []graph = new Vector[100];
static String []weight = new String[100];
 
// Function that returns if the
// String x is a pangram
static boolean Pangram(String x)
{
    HashMap<Character, Integer> mp = new HashMap<>();
    int n = x.length();
 
    for(int i = 0 ; i < n; i++)
    {
        if (mp.containsKey(x.charAt(i)))
        {
            mp.put(x.charAt(i),
            mp.get(x.charAt(i)) + 1);
        }
        else
        {
            mp.put(x.charAt(i), 1);
        }
    }
    if (mp.size() == 26)
        return true;
    else
        return false;
}
 
// Function to return the count of nodes
// which make pangram with the
// sub-tree nodes
static int countTotalPangram(int n)
{
    int cnt = 0;
    for(int i = 1; i <= n; i++)
        if (Pangram(weight[i]))
            cnt++;
             
    return cnt;
}
 
// Function to perform dfs and update the nodes
// such that weight[i] will store the weight[i]
// concatenated with the weights of
// all the nodes in the sub-tree
static void dfs(int node, int parent)
{
    for(int to : graph[node])
    {
        if (to == parent)
            continue;
             
        dfs(to, node);
        weight[node] += weight[to];
    }
}
 
// Driver code
public static void main(String[] args)
{
    int n = 6;
 
    // Weights of the nodes
    weight[1] = "abcde";
    weight[2] = "fghijkl";
    weight[3] = "abcdefg";
    weight[4] = "mnopqr";
    weight[5] = "stuvwxy";
    weight[6] = "zabcdef";
 
    for(int i = 0; i < graph.length; i++)
        graph[i] = new Vector<Integer>();
         
    // Edges of the tree
    graph[1].add(2);
    graph[2].add(3);
    graph[2].add(4);
    graph[1].add(5);
    graph[5].add(6);
 
    dfs(1, 1);
 
    System.out.print(countTotalPangram(n));
}
}
 
// This code is contributed by Amit Katiyar

# Python3 implementation of the approach
graph = [[] for i in range(100)]
weight = [0] * 100
 
# Function that returns if the
# string x is a pangram
def Pangram(x):
    mp = {}
    n = len(x)
    for i in range(n):
        if x[i] not in mp:
            mp[x[i]] = 0
        mp[x[i]] += 1
    if (len(mp)== 26):
        return True
    else:
        return False
 
# Function to return the count of nodes
# which make pangram with the
# sub-tree nodes
def countTotalPangram(n):
    cnt = 0
    for i in range(1, n + 1):
        if (Pangram(weight[i])):
            cnt += 1
    return cnt
 
# Function to perform dfs and update the nodes
# such that weight[i] will store the weight[i]
# concatenated with the weights of
# all the nodes in the sub-tree
def dfs(node, parent):
    for to in graph[node]:
        if (to == parent):
            continue
        dfs(to, node)
        weight[node] += weight[to]
 
# Driver code
n = 6
 
# Weights of the nodes
weight[1] = "abcde"
weight[2] = "fghijkl"
weight[3] = "abcdefg"
weight[4] = "mnopqr"
weight[5] = "stuvwxy"
weight[6] = "zabcdef"
 
# Edges of the tree
graph[1].append(2)
graph[2].append(3)
graph[2].append(4)
graph[1].append(5)
graph[5].append(6)
 
dfs(1, 1)
print(countTotalPangram(n))
 
# This code is contributed by SHUBHAMSINGH10

// C# implementation of
// the above approach
using System;
using System.Collections.Generic;
class GFG{   
 
static List<int> []graph =
            new List<int>[100];
static String []weight =
                new String[100];
 
// Function that returns if the
// String x is a pangram
static bool Pangram(String x)
{
  Dictionary<char,
             int> mp = new Dictionary<char,
                                      int>();
  int n = x.Length;
 
  for(int i = 0 ; i < n; i++)
  {
    if (mp.ContainsKey(x[i]))
    {
      mp[x[i]] = mp[x[i]] + 1;
    }
    else
    {
      mp.Add(x[i], 1);
    }
  }
  if (mp.Count == 26)
    return true;
  else
    return false;
}
 
// Function to return the
// count of nodes which
// make pangram with the
// sub-tree nodes
static int countTotalPangram(int n)
{
  int cnt = 0;
  for(int i = 1; i <= n; i++)
    if (Pangram(weight[i]))
      cnt++;
 
  return cnt;
}
 
// Function to perform dfs and
// update the nodes such that
// weight[i] will store the weight[i]
// concatenated with the weights of
// all the nodes in the sub-tree
static void dfs(int node, int parent)
{
  foreach(int to in graph[node])
  {
    if (to == parent)
      continue;
 
    dfs(to, node);
    weight[node] += weight[to];
  }
}
 
// Driver code
public static void Main(String[] args)
{
  int n = 6;
 
  // Weights of the nodes
  weight[1] = "abcde";
  weight[2] = "fghijkl";
  weight[3] = "abcdefg";
  weight[4] = "mnopqr";
  weight[5] = "stuvwxy";
  weight[6] = "zabcdef";
 
  for(int i = 0;
          i < graph.Length; i++)
    graph[i] = new List<int>();
 
  // Edges of the tree
  graph[1].Add(2);
  graph[2].Add(3);
  graph[2].Add(4);
  graph[1].Add(5);
  graph[5].Add(6);
 
  dfs(1, 1);
  Console.Write(countTotalPangram(n));
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// JavaScript implementation of the approach
 
 
let graph = new Array();
 
for (let i = 0; i < 100; i++) {
    graph.push([])
}
let weight = new Array(100).fill(0);
 
// Function that returns if the
// string x is a pangram
function Pangram(x) {
    let mp = new Map();
    let n = x.length;
 
    for (let i = 0; i < n; i++) {
        if (mp.has(x[i])) {
            mp.set(x[i], mp.get(x[i]) + 1)
        } else {
            mp.set(x[i], 1)
        }
    }
 
    if (mp.size == 26)
        return true;
    else
        return false;
}
 
// Function to return the count of nodes
// which make pangram with the
// sub-tree nodes
function countTotalPangram(n) {
    let cnt = 0;
    for (let i = 1; i <= n; i++)
        if (Pangram(weight[i]))
            cnt++;
    return cnt;
}
 
// Function to perform dfs and update the nodes
// such that weight[i] will store the weight[i]
// concatenated with the weights of
// all the nodes in the sub-tree
function dfs(node, parent) {
 
    for (let to of graph[node]) {
        if (to == parent)
            continue;
        dfs(to, node);
        weight[node] += weight[to];
    }
}
 
// Driver code
 
let n = 6;
 
// Weights of the nodes
weight[1] = "abcde";
weight[2] = "fghijkl";
weight[3] = "abcdefg";
weight[4] = "mnopqr";
weight[5] = "stuvwxy";
weight[6] = "zabcdef";
 
// Edges of the tree
graph[1].push(2);
graph[2].push(3);
graph[2].push(4);
graph[1].push(5);
graph[5].push(6);
 
dfs(1, 1);
 
document.write(countTotalPangram(n));
 
 
// This code is contributed by gfgking
 
</script>

1

Análisis de Complejidad: 

• Complejidad temporal: O(N*S). 
  En dfs, cada Node del árbol se procesa una vez y, por lo tanto, la complejidad debida a dfs es O(N) si hay un total de N Nodes en el árbol. Además, para procesar cada Node, se usa la función Pangram() para cada Node que tiene una complejidad de O(S) donde S es la suma de la longitud de todas las strings de peso en un subárbol y dado que esto se hace para cada Node, el la complejidad de tiempo total para esta parte se convierte en O(N*S). Por lo tanto, la complejidad temporal final es O(N*S).
• Espacio Auxiliar: O(1). 
  No se requiere ningún espacio adicional, por lo que la complejidad del espacio es constante.