Given a tree, and the weights (in the form of strings) of all the nodes, the task is to count the nodes whose weights are palindrome.
Examples:
Input:
Output: 3
Only the weights of the nodes 2, 3 and 5 are palindromes.
Approach: Perform dfs on the tree and for every node, check if it’s string is palindrome or not. If yes then increment the count.
Implementation:
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 palindromebool 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 dfsvoid 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 codeint 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
// 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
# Python3 implementation of the approachcnt = 0graph = [0] * 100for i in range(100): graph[i] = []weight = ["0"] * 100# Function that returns true# if x is a palindromedef 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 dfsdef 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 Codeif __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#
// 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 |
Javascript
<script> // Javascript implementation of the approachlet 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 palindromefunction 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 dfsfunction 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 nodeweight[1] = "abc";weight[2] = "aba";weight[3] = "bcb";weight[4] = "moh";weight[5] = "aa";// Edges of the treegraph[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> |
Output
3
Complexity Analysis:
- Time Complexity: O(N*Len) where Len is the maximum length of the weighted string of a node in the given tree.
In DFS, every node of the tree is processed once and hence the complexity due to the DFS is O(N) for N nodes in the tree. Also, processing of every node involves traversing the weighted string of that node once, thus adding a complexity of O(Len) where Len is the length of the weighted string. Therefore, the total time complexity is O(N*Len). - Auxiliary Space: O(1).
Any extra space is not required, so the space complexity is constant.
New Approach : (BFS)
- This implementation uses a queue to perform a breadth-first search starting from the root node (node 1).
- It iteratively visits each node and checks if its weight is a palindrome.
- If it is, the count is incremented.
- The neighbors of each node are added to the queue for further exploration.
- Finally, the count of nodes with palindrome weights is returned.
Bellow is the implementation of the approach ;
C++
#include <iostream>#include <deque>#include <unordered_map>#include <vector>#include <string>using namespace std;bool is_palindrome(const string& x) { return x == string(x.rbegin(), x.rend());}int count_palindrome_nodes(const unordered_map<int, vector<int>>& graph, const vector<string>& weight) { int count = 0; deque<int> queue; queue.push_back(1); // Start the BFS from node 1 (root) while (!queue.empty()) { int node = queue.front(); queue.pop_front(); if (is_palindrome(weight[node])) { count++; } for (int neighbor : graph.at(node)) { queue.push_back(neighbor); } } return count;}int main() { // Weights of the nodes vector<string> weight = {"", "abc", "aba", "bcb", "moh", "aa"}; // Edges of the tree unordered_map<int, vector<int>> graph = { {1, {2, 5}}, {2, {3, 4}}, {3, {}}, {4, {}}, {5, {}} }; int result = count_palindrome_nodes(graph, weight); cout << result << endl; return 0;} |
Java
import java.util.*;public class GFG { // Function to check if a string is a palindrome static boolean isPalindrome(String x) { return x.equals( new StringBuilder(x).reverse().toString()); } // Function to count palindrome nodes in the tree static int countPalindromeNodes( HashMap<Integer, List<Integer> > graph, List<String> weight) { int count = 0; Deque<Integer> queue = new LinkedList<>(); queue.add(1); // Start the BFS from node 1 (root) while (!queue.isEmpty()) { int node = queue.poll(); if (isPalindrome(weight.get(node))) { count++; } for (int neighbor : graph.getOrDefault( node, Collections.emptyList())) { queue.add(neighbor); } } return count; } public static void main(String[] args) { // Weights of the nodes List<String> weight = new ArrayList<>(Arrays.asList( "", "abc", "aba", "bcb", "moh", "aa")); // Edges of the tree HashMap<Integer, List<Integer> > graph = new HashMap<>(); graph.put(1, new ArrayList<>(Arrays.asList(2, 5))); graph.put(2, new ArrayList<>(Arrays.asList(3, 4))); graph.put(3, new ArrayList<>()); graph.put(4, new ArrayList<>()); graph.put(5, new ArrayList<>()); int result = countPalindromeNodes(graph, weight); System.out.println(result); }} |
Python
from collections import dequedef is_palindrome(x): return x == x[::-1]def count_palindrome_nodes(graph, weight): count = 0 queue = deque() queue.append(1) # Start the BFS from node 1 (root) while queue: node = queue.popleft() if is_palindrome(weight[node]): count += 1 for neighbor in graph[node]: queue.append(neighbor) return count# Example usage:# Weights of the nodesweight = ["", "abc", "aba", "bcb", "moh", "aa"]# Edges of the treegraph = { 1: [2, 5], 2: [3, 4], 3: [], 4: [], 5: []}result = count_palindrome_nodes(graph, weight)print(result) |
C#
using System;using System.Collections.Generic;class GFG{ static bool IsPalindrome(string x) { char[] charArray = x.ToCharArray(); Array.Reverse(charArray); string reversed = new string(charArray); return x == reversed; } static int CountPalindromeNodes(Dictionary<int, List<int>> graph, List<string> weight) { int count = 0; Queue<int> queue = new Queue<int>(); queue.Enqueue(1); // Start the BFS from node 1 (root) while (queue.Count > 0) { int node = queue.Dequeue(); if (IsPalindrome(weight[node])) { count++; } foreach (int neighbor in graph[node]) { queue.Enqueue(neighbor); } } return count; } static void Main(string[] args) { // Weights of the nodes List<string> weight = new List<string> { "", "abc", "aba", "bcb", "moh", "aa" }; // Edges of the tree Dictionary<int, List<int>> graph = new Dictionary<int, List<int>> { { 1, new List<int> { 2, 5 } }, { 2, new List<int> { 3, 4 } }, { 3, new List<int>() }, { 4, new List<int>() }, { 5, new List<int>() } }; int result = CountPalindromeNodes(graph, weight); Console.WriteLine(result); }} |
Javascript
// Function to check if a string is a palindromefunction is_palindrome(x) { return x === x.split("").reverse().join("");} // Function to count palindrome nodes in the treefunction count_palindrome_nodes(graph, weight) { let count = 0; let queue = []; queue.push(1); // Start the BFS from node 1 (root) while (queue.length > 0) { let node = queue.shift(); if (is_palindrome(weight[node])) { count++; } let neighbors = graph[node]; for (let neighbor of neighbors) { queue.push(neighbor); } } return count;}let weight = { 1: "abc", 2: "aba", 3: "bcb", 4: "moh", 5: "aa"};// Edges of the treelet graph = { 1: [2, 5], 2: [3, 4], 3: [], 4: [], 5: []};let result = count_palindrome_nodes(graph, weight);console.log(result);// This Code Is Contributed By Shubham Tiwari |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
