Dado un árbol N-ario , y los pesos que están en forma de strings de todos los Nodes, la tarea es contar el número de Nodes hoja cuyos pesos son palíndromos.
Ejemplos:
Input:
1(ab)
/ \
(abca)2 5 (aba)
/ \
(axxa)3 4 (geeks)
Output: 2
Explanation:
Only the weights of the leaf nodes
"axxa" and "aba" are palindromes.
Input:
1(abx)
/
2(abaa)
/
3(amma)
Output: 1
Explanation:
Only the weight of the leaf
node "amma" is palindrome.
Enfoque: Para resolver el problema mencionado anteriormente, siga los pasos que se detallan a continuación:
- La primera búsqueda en profundidad se puede utilizar para recorrer el árbol completo.
- Realizaremos un seguimiento de los padres durante el recorrido para evitar la array de Nodes visitada.
- Inicialmente, para cada Node, podemos establecer una bandera y si el Node tiene al menos un hijo (es decir, un Node que no sea hoja), restableceremos la bandera.
- Los Nodes sin hijos son los Nodes hoja. Para cada Node de hoja, verificaremos si su string es palíndromo o no. Si es así, entonces 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 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 on the tree
void dfs(int node, int parent)
{
int flag = 1;
// Iterating the children of current node
for (int to : graph[node]) {
// There is at least a child
// of the current node
if (to == parent)
continue;
flag = 0;
dfs(to, node);
}
// Current node is connected to only
// its parent i.e. it is a leaf node
if (flag == 1) {
// Weight of the current node
string x = weight[node];
// If the weight is a palindrome
if (isPalindrome(x))
cnt += 1;
}
}
// Driver code
int main()
{
// Weights of the node
weight[1] = "ab";
weight[2] = "abca";
weight[3] = "axxa";
weight[4] = "geeks";
weight[5] = "aba";
// 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
// Java implementation of the approach
import java.util.*;
class GFG{
static int cnt = 0;
static Vector<Integer> []graph = new Vector[100];
static String []weight = new String[100];
// 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 on the tree
static void dfs(int node, int parent)
{
int flag = 1;
// Iterating the children of current node
for (int to : graph[node])
{
// There is at least a child
// of the current node
if (to == parent)
continue;
flag = 0;
dfs(to, node);
}
// Current node is connected to only
// its parent i.e. it is a leaf node
if (flag == 1)
{
// Weight of the current node
String x = weight[node];
// If the weight is a palindrome
if (isPalindrome(x))
cnt += 1;
}
}
// Driver code
public static void main(String[] args)
{
for(int i = 0; i < graph.length;i++)
graph[i] = new Vector<Integer>();
// Weights of the node
weight[1] = "ab";
weight[2] = "abca";
weight[3] = "axxa";
weight[4] = "geeks";
weight[5] = "aba";
// Edges of the tree
graph[1].add(2);
graph[2].add(3);
graph[2].add(4);
graph[1].add(5);
dfs(1, 1);
System.out.print(cnt);
}
}
// This code is contributed by amal kumar choubey
Python3
# 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: str) -> bool: n = len(x) for i in range(n // 2): if (x[i] != x[n - 1 - i]): return False return True # Function to perform DFS on the tree def dfs(node: int, parent: int) -> None: global cnt, graph, weight flag = 1 # Iterating the children of current node for to in graph[node]: # There is at least a child # of the current node if (to == parent): continue flag = 0 dfs(to, node) # Current node is connected to only # its parent i.e. it is a leaf node if (flag == 1): # Weight of the current node x = weight[node] # If the weight is a palindrome if (isPalindrome(x)): cnt += 1 # Driver code if __name__ == "__main__": # Weights of the node weight[1] = "ab" weight[2] = "abca" weight[3] = "axxa" weight[4] = "geeks" weight[5] = "aba" # 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#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG{
static int cnt = 0;
static List<int> []graph = new List<int>[100];
static String []weight = new String[100];
// 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 on the tree
static void dfs(int node, int parent)
{
int flag = 1;
// Iterating the children of
// current node
foreach (int to in graph[node])
{
// There is at least a child
// of the current node
if (to == parent)
continue;
flag = 0;
dfs(to, node);
}
// Current node is connected to only
// its parent i.e. it is a leaf node
if (flag == 1)
{
// Weight of the current node
String x = weight[node];
// If the weight is a palindrome
if (isPalindrome(x))
cnt += 1;
}
}
// Driver code
public static void Main(String[] args)
{
for(int i = 0; i < graph.Length; i++)
graph[i] = new List<int>();
// Weights of the node
weight[1] = "ab";
weight[2] = "abca";
weight[3] = "axxa";
weight[4] = "geeks";
weight[5] = "aba";
// Edges of the tree
graph[1].Add(2);
graph[2].Add(3);
graph[2].Add(4);
graph[1].Add(5);
dfs(1, 1);
Console.Write(cnt);
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// JavaScript implementation of the approach
let cnt = 0;
let graph = new Array(100);
let weight = new Array(100);
// Function that returns true
// if x is a palindrome
function isPalindrome(x)
{
let n = x.length;
for (let i = 0; i < parseInt(n / 2, 10); i++)
{
if (x[i] != x[n - 1 - i])
return false;
}
return true;
}
// Function to perform DFS on the tree
function dfs(node, parent)
{
let flag = 1;
// Iterating the children of current node
for (let to = 0; to < graph[node].length; to++)
{
// There is at least a child
// of the current node
if (graph[node][to] == parent)
continue;
flag = 0;
dfs(graph[node][to], node);
}
// Current node is connected to only
// its parent i.e. it is a leaf node
if (flag == 1)
{
// Weight of the current node
let x = weight[node];
// If the weight is a palindrome
if (isPalindrome(x))
cnt += 1;
}
}
for(let i = 0; i < graph.length;i++)
graph[i] = [];
// Weights of the node
weight[1] = "ab";
weight[2] = "abca";
weight[3] = "axxa";
weight[4] = "geeks";
weight[5] = "aba";
// 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);
</script>
Producción:
2
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA