Leetcode 3327. Check if DFS Strings Are Palindromes
- Leetcode 3327. Check if DFS Strings Are Palindromes
- 1. 解题思路
- 2. 代码实现
- 题目链接:3327. Check if DFS Strings Are Palindromes
1. 解题思路
这一题其实不太理解为什么会是一个hard的题目,就是一个简单的dfs算法,我们构造出这个树然后做一次深度优先遍历找出每一个节点对应的dfsStr,然后判断其是否为回文序列即可。
2. 代码实现
给出python代码实现如下:
class Solution:
def findAnswer(self, parent: List[int], s: str) -> List[bool]:
if len(set(s)) == 1:
return [True for _ in parent]
n = len(parent)
graph = defaultdict(list)
for i in range(n):
graph[parent[i]].append(i)
ans = [False for _ in range(n)]
def dfs(root):
nonlocal ans
dfs_str = ""
for u in graph[root]:
dfs_str += dfs(u)
dfs_str += s[root]
n = len(dfs_str)
ans[root] = (dfs_str == dfs_str[::-1])
return dfs_str
dfs(0)
return ans
提交代码评测得到:耗时6643ms,占用内存72.9MB。