LeetCode 3327: Check if DFS Strings Are Palindromes
Problem Description
Explanation
To solve this problem, we will perform a Depth-First Search (DFS) traversal on the tree rooted at node 0. At each node, we will recursively traverse its children in increasing order and construct a string dfsStr by appending the characters of the nodes. After visiting all children, we check if the constructed string dfsStr is a palindrome or not. Based on this check, we update the boolean array answer accordingly. We repeat this process for all nodes in the tree.
Time Complexity
The time complexity of this solution is O(n) where n is the number of nodes in the tree.
Space Complexity
The space complexity of this solution is O(n) for the boolean array answer, the string dfsStr, and the recursive stack used in the DFS traversal.
Solutions
class Solution {
public boolean[] checkIfDfsStringsArePalindromes(int[] parent, String s) {
int n = parent.length;
boolean[] answer = new boolean[n];
ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < n; i++) {
adjList.add(new ArrayList<>());
}
for (int i = 1; i < n; i++) {
adjList.get(parent[i]).add(i);
}
for (int i = 0; i < n; i++) {
StringBuilder dfsStr = new StringBuilder();
dfs(i, adjList, s, dfsStr);
answer[i] = isPalindrome(dfsStr.toString());
}
return answer;
}
private void dfs(int x, ArrayList<ArrayList<Integer>> adjList, String s, StringBuilder dfsStr) {
for (int child : adjList.get(x)) {
dfs(child, adjList, s, dfsStr);
}
dfsStr.append(s.charAt(x));
}
private boolean isPalindrome(String str) {
int left = 0, right = str.length() - 1;
while (left < right) {
if (str.charAt(left) != str.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
}Loading editor...