Cuente los Nodes del árbol dado cuya string ponderada es un palíndromo

Dado un árbol y los pesos (en forma de strings) de todos los Nodes, la tarea es contar los Nodes cuyos pesos son palíndromos.

Ejemplos: 

Input: 

Output: 3
Only the weights of the nodes 2, 3 and 5 are palindromes.

Enfoque: Realice dfs en el árbol y para cada Node, verifique si su string es palíndromo o no. Si es así, entonces incremente el conteo.

Implementación: 

// 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 x is a palindrome
bool isPalindrome(string x)
{
    int n = x.size();
    for (int i = 0; i < n / 2; i++) {
        if (x[i] != x[n - 1 - i])
            return false;
    }
    return true;
}
 
// Function to perform dfs
void dfs(int node, int parent)
{
 
    // Weight of the current node
    string x = weight[node];
 
    // If the weight is a palindrome
    if (isPalindrome(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] = "abc";
    weight[2] = "aba";
    weight[3] = "bcb";
    weight[4] = "moh";
    weight[5] = "aa";
 
    // Edges of the tree
    graph[1].push_back(2);
    graph[2].push_back(3);
    graph[2].push_back(4);
    graph[1].push_back(5);
 
    dfs(1, 1);
 
    cout << cnt;
 
    return 0;
}

// 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 x is a palindrome
static boolean isPalindrome(String x)
{
    int n = x.length();
    for (int i = 0; i < n / 2; i++)
    {
        if (x.charAt(i) != x.charAt(n - 1 - i))
            return false;
    }
    return true;
}
 
// Function to perform dfs
static void dfs(int node, int parent)
{
 
    // Weight of the current node
    String x = weight.get(node);
     
 
    // If the weight is a palindrome
    if (isPalindrome(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( "abc");
    weight.add( "aba");
    weight.add( "bcb");
    weight.add( "moh");
    weight.add( "aa");
     
    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);
    dfs(1, 1);
 
    System.out.println( cnt);
}
}
 
// This code is contributed by Arnab Kundu

# Python3 implementation of the approach
cnt = 0
 
graph = [0] * 100
for i in range(100):
    graph[i] = []
 
weight = ["0"] * 100
 
# Function that returns true
# if x is a palindrome
def isPalindrome(x):
    n = len(x)
 
    for i in range(0, n // 2):
        if x[i] != x[n - 1 - i]:
            return False
 
    return True
 
# Function to perform dfs
def dfs(node, parent):
    global cnt
 
    # Weight of the current node
    x = weight[node]
 
    # If the weight is a palindrome
    if (isPalindrome(x)):
        cnt += 1
 
    for to in graph[node]:
        if to == parent:
            continue
        dfs(to, node)
 
# Driver Code
if __name__ == "__main__":
 
    # Weights of the node
    weight[0] = ""
    weight[1] = "abc"
    weight[2] = "aba"
    weight[3] = "bcb"
    weight[4] = "moh"
    weight[5] = "aa"
 
    # Edges of the tree
    graph[1].append(2)
    graph[2].append(3)
    graph[2].append(4)
    graph[1].append(5)
 
    dfs(1, 1)
 
    print(cnt)
 
# This code is contributed by
# sanjeev2552

// 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 x is a palindrome
    static bool isPalindrome(string x)
    {
        int n = x.Length;
        for (int i = 0; i < n / 2; i++)
        {
            if (x[i] != x[n - 1 - i])
                return false;
        }
        return true;
    }
     
    // Function to perform dfs
    static void dfs(int node, int parent)
    {
     
        // Weight of the current node
        String x = weight[node];
     
        // If the weight is a palindrome
        if (isPalindrome(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( "abc");
        weight.Add( "aba");
        weight.Add( "bcb");
        weight.Add( "moh");
        weight.Add( "aa");
         
        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);
     
        dfs(1, 1);
     
        Console.WriteLine( cnt);
     
    }
}
 
// This code has been contributed by 29AjayKumar

<script>
  
// Javascript implementation of the approach
let cnt = 0;
 
let graph = new Array(100);
let weight = new Array(100);
for(let i = 0; i < 100; i++)
{
    graph[i] = [];
    weight[i] = 0;
}
 
// Function that returns true
// if x is a palindrome
function isPalindrome(x)
{
    let n = x.length;
    for(let i = 0; i < n / 2; i++)
    {
        if (x[i] != x[n - 1 - i])
            return false;
    }
    return true;
}
 
// Function to perform dfs
function dfs(node, parent)
{
 
    // Weight of the current node
    let x = weight[node];
 
    // If the weight is a palindrome
    if (isPalindrome(x))
        cnt += 1;
         
    for(let to = 0; to < graph[node].length; to++)
    {
        if (graph[node][to] == parent)
            continue
             
        dfs(graph[node][to], node); 
    }
}
 
// Driver code
     
// Weights of the node
weight[1] = "abc";
weight[2] = "aba";
weight[3] = "bcb";
weight[4] = "moh";
weight[5] = "aa";
 
// Edges of the tree
graph[1].push(2);
graph[2].push(3);
graph[2].push(4);
graph[1].push(5);
 
dfs(1, 1);
 
document.write(cnt);
 
// This code is contributed by Dharanendra L V.
      
</script>

3

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.