3327. Check if DFS Strings Are Palindromes LeetCode Solution
In this guide, you will get 3327. Check if DFS Strings Are Palindromes LeetCode Solution with the best time and space complexity. The solution to Check if DFS Strings Are Palindromes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Check if DFS Strings Are Palindromes solution in C++
- Check if DFS Strings Are Palindromes solution in Java
- Check if DFS Strings Are Palindromes solution in Python
- Additional Resources
Problem Statement of Check if DFS Strings Are Palindromes
You are given a tree rooted at node 0, consisting of n nodes numbered from 0 to n – 1. The tree is represented by an array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1.
You are also given a string s of length n, where s[i] is the character assigned to node i.
Consider an empty string dfsStr, and define a recursive function dfs(int x) that takes a node x as a parameter and performs the following steps in order:
Iterate over each child y of x in increasing order of their numbers, and call dfs(y).
Add the character s[x] to the end of the string dfsStr.
Note that dfsStr is shared across all recursive calls of dfs.
You need to find a boolean array answer of size n, where for each index i from 0 to n – 1, you do the following:
Empty the string dfsStr and call dfs(i).
If the resulting string dfsStr is a palindrome, then set answer[i] to true. Otherwise, set answer[i] to false.
Return the array answer.
Example 1:
Input: parent = [-1,0,0,1,1,2], s = “aababa”
Output: [true,true,false,true,true,true]
Explanation:
Calling dfs(0) results in the string dfsStr = “abaaba”, which is a palindrome.
Calling dfs(1) results in the string dfsStr = “aba”, which is a palindrome.
Calling dfs(2) results in the string dfsStr = “ab”, which is not a palindrome.
Calling dfs(3) results in the string dfsStr = “a”, which is a palindrome.
Calling dfs(4) results in the string dfsStr = “b”, which is a palindrome.
Calling dfs(5) results in the string dfsStr = “a”, which is a palindrome.
Example 2:
Input: parent = [-1,0,0,0,0], s = “aabcb”
Output: [true,true,true,true,true]
Explanation:
Every call on dfs(x) results in a palindrome string.
Constraints:
n == parent.length == s.length
1 <= n <= 105
0 <= parent[i] = 1.
parent[0] == -1
parent represents a valid tree.
s consists only of lowercase English letters.
Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(n)
3327. Check if DFS Strings Are Palindromes LeetCode Solution in C++
class Solution {
public:
vector<bool> findAnswer(vector<int>& parent, string s) {
const int n = parent.size();
vector<bool> ans(n);
vector<vector<int>> tree(n);
vector<int> start(n); // start[i] := the start index of `dfsStr` of node i
vector<int> end(n); // end[i] := the end index of `dfsStr` of node i
string dfsStr;
for (int i = 1; i < n; ++i)
tree[parent[i]].push_back(i);
dfs(tree, 0, /*index=*/0, s, start, end, dfsStr);
const string t = join('@' + dfsStr + '$', /*delimiter=*/'#');
const vector<int> p = manacher(t);
for (int i = 0; i < n; ++i)
ans[i] = isPalindrome(start[i], end[i], p);
return ans;
}
private:
// Returns the start index of the "DFS string" of u's next node.
int dfs(const vector<vector<int>>& tree, int u, int index, const string& s,
vector<int>& start, vector<int>& end, string& dfsStr) {
start[u] = index;
for (const int v : tree[u])
index = dfs(tree, v, index, s, start, end, dfsStr);
end[u] = index;
dfsStr += s[u];
return index + 1;
}
// Returns an array `p` s.t. `p[i]` is the length of the longest palindrome
// centered at `t[i]`, where `t` is a string with delimiters and sentinels.
vector<int> manacher(const string& t) {
vector<int> p(t.length());
int center = 0;
for (int i = 1; i < t.length() - 1; ++i) {
const int rightBoundary = center + p[center];
const int mirrorIndex = center - (i - center);
if (rightBoundary > i)
p[i] = min(rightBoundary - i, p[mirrorIndex]);
// Try to expand the palindrome centered at i.
while (t[i + 1 + p[i]] == t[i - 1 - p[i]])
++p[i];
// If a palindrome centered at i expands past `rightBoundary`, adjust
// the center based on the expanded palindrome.
if (i + p[i] > rightBoundary)
center = i;
}
return p;
}
// Returns true if `dfsStr[s..e]` is a palindrome by using the precomputed
// array `p` from the Manacher's algorithm.
//
// The precomputed array `p` is based on the string `t` with delimiters and
// sentinels. Let `t = '#'.join('@' + dfsStr + '$')`. Then, the center of
// `dfsStr` maps to `t[s + e + 2]` since `dfsStr[s]` maps to `t[2 * s + 2]`
// and `dfsStr[e]` maps to `t[2 * e + 2]`. So, the center of `dfsStr` is
// `t[(2 * s + 2 + 2 * e + 2) / 2] = t[s + e + 2]`.
bool isPalindrome(int s, int e, const vector<int>& p) {
const int length = e - s + 1;
const int center = s + e + 2;
return p[center] >= length;
}
string join(const string& s, char delimiter) {
string joined;
for (int i = 0; i < s.length() - 1; ++i) {
joined += s[i];
joined += delimiter;
}
joined += s.back();
return joined;
}
};
/* code provided by PROGIEZ */3327. Check if DFS Strings Are Palindromes LeetCode Solution in Java
class Solution {
public boolean[] findAnswer(int[] parent, String s) {
final int n = parent.length;
boolean[] ans = new boolean[n];
List<Integer>[] tree = new List[n];
// start[i] := the start index of `dfsStr` of node i
int[] start = new int[n];
// end[i] := the end index of `dfsStr` of node i
int[] end = new int[n];
for (int i = 0; i < n; ++i)
tree[i] = new ArrayList<>();
StringBuilder dfsStr = new StringBuilder();
for (int i = 1; i < n; ++i)
tree[parent[i]].add(i);
dfs(tree, 0, /*index=*/0, s, start, end, dfsStr);
final String t = join('@' + dfsStr.toString() + '$', '#');
final int[] p = manacher(t);
for (int i = 0; i < n; ++i)
ans[i] = isPalindrome(start[i], end[i], p);
return ans;
}
// Returns the start index of the "DFS string" of u's next node.
private int dfs(List<Integer>[] tree, int u, int index, final String s, int[] start, int[] end,
StringBuilder dfsStr) {
start[u] = index;
for (final int v : tree.get(u))
index = dfs(tree, v, index, s, start, end, dfsStr);
end[u] = index;
dfsStr.append(s.charAt(u));
return index + 1;
}
// Returns true if `dfsStr[s..e]` is a palindrome by using the precomputed
// array `p` from the Manacher's algorithm.
//
// The precomputed array `p` is based on the string `t` with delimiters and
// sentinels. Let `t = '#'.join('@' + dfsStr + '$')`. Then, the center of
// `dfsStr` maps to `t[s + e + 2]` since `dfsStr[s]` maps to `t[2 * s + 2]`
// and `dfsStr[e]` maps to `t[2 * e + 2]`. So, the center of `dfsStr` is
// `t[(2 * s + 2 + 2 * e + 2) / 2] = t[s + e + 2]`.
private boolean isPalindrome(int s, int e, int[] p) {
final int length = e - s + 1;
final int center = s + e + 2;
return p[center] >= length;
}
// Returns an array `p` s.t. `p[i]` is the length of the longest palindrome
// centered at `t[i]`, where `t` is a string with delimiters and sentinels.
private int[] manacher(final String t) {
int[] p = new int[t.length()];
int center = 0;
for (int i = 1; i < t.length() - 1; ++i) {
int rightBoundary = center + p[center];
int mirrorIndex = center - (i - center);
if (rightBoundary > i)
p[i] = Math.min(rightBoundary - i, p[mirrorIndex]);
// Try to expand the palindrome centered at i.
while (i + 1 + p[i] < t.length() && i - 1 - p[i] >= 0 &&
t.charAt(i + 1 + p[i]) == t.charAt(i - 1 - p[i]))
++p[i];
// If a palindrome centered at i expands past `rightBoundary`, adjust
// the center based on the expanded palindrome.
if (i + p[i] > rightBoundary) {
center = i;
}
}
return p;
}
private String join(final String s, char delimiter) {
StringBuilder joined = new StringBuilder();
for (int i = 0; i < s.length() - 1; ++i) {
joined.append(s.charAt(i));
joined.append(delimiter);
}
joined.append(s.charAt(s.length() - 1));
return joined.toString();
}
}
// code provided by PROGIEZ3327. Check if DFS Strings Are Palindromes LeetCode Solution in Python
class Solution:
def findAnswer(self, parent: list[int], s: str) -> list[bool]:
n = len(parent)
tree = [[] for _ in parent]
start = [0] * n # start[i] := the start index of `dfsStr` of node i
end = [0] * n # end[i] := the end index of `dfsStr` of node i
dfsStr = []
for i in range(1, n):
tree[parent[i]].append(i)
self._dfs(tree, 0, 0, s, start, end, dfsStr)
t = '#'.join('@' + ''.join(dfsStr) + '$')
p = self._manacher(t)
return [self._isPalindrome(s, e, p)
for s, e in zip(start, end)]
def _dfs(
self,
tree: list[list[int]],
u: int,
index: int,
s: str,
start: list[int],
end: list[int],
dfsStr: list[str]
) -> int:
"""Returns the start index of the "DFS string" of u's next node."""
start[u] = index
for v in tree[u]:
index = self._dfs(tree, v, index, s, start, end, dfsStr)
end[u] = index
dfsStr.append(s[u])
return index + 1
def _manacher(self, t: str) -> list[int]:
"""
Returns an array `p` s.t. `p[i]` is the length of the longest palindrome
centered at `t[i]`, where `t` is a string with delimiters and sentinels.
"""
p = [0] * len(t)
center = 0
for i in range(1, len(t) - 1):
rightBoundary = center + p[center]
mirrorIndex = center - (i - center)
if rightBoundary > i:
p[i] = min(rightBoundary - i, p[mirrorIndex])
# Try to expand the palindrome centered at i.
while t[i + 1 + p[i]] == t[i - 1 - p[i]]:
p[i] += 1
# If a palindrome centered at i expands past `rightBoundary`, adjust
# the center based on the expanded palindrome.
if i + p[i] > rightBoundary:
center = i
return p
def _isPalindrome(self, s: int, e: int, p: list[int]) -> bool:
"""
Returns true if `dfsStr[s..e]` is a palindrome by using the precomputed
array `p` from the Manacher's algorithm.
The precomputed array `p` is based on the string `t` with delimiters and
sentinels. Let `t = '#'.join('@' + dfsStr + '$')`. Then, the center of
`dfsStr` maps to `t[s + e + 2]` since `dfsStr[s]` maps to `t[2 * s + 2]`
and `dfsStr[e]` maps to `t[2 * e + 2]`. So, the center of `dfsStr` is
`t[(2 * s + 2 + 2 * e + 2) / 2] = t[s + e + 2]`.
"""
length = e - s + 1
center = s + e + 2
return p[center] >= length
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.