Leetcode 3615. Longest Palindromic Path in Graph

• Leetcode 3615. Longest Palindromic Path in Graph
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3615. Longest Palindromic Path in Graph

1. 解题思路

这一题思路上就是一个动态规划的思路，我们只需要考察每一个节点作为中心节点时，其两侧辐射下去最长能够达到的长度即可。

考虑到路径不能重复经过同一个点，因此我们需要给定status来记录每一个点是否曾经走过，这个我们可以通过一个常数来记录，其每一个二进制位都表示对应节点是否有被走过。

2. 代码实现

给出python代码实现如下：

class Solution:def maxLen(self, n: int, edges: List[List[int]], label: str) -> int:graph = defaultdict(list)for u, v in edges:graph[u].append(v)graph[v].append(u)@lru_cache(None)def dfs(u1, u2, status):if u1 > u2:return dfs(u2, u1, status)ans = 2status = status | (1<<u1) | (1<<u2)for v1 in graph[u1]:if status & (1<<v1) != 0:continuefor v2 in graph[u2]:if status & (1<<v2) != 0:continueif v1 != v2 and label[v1] == label[v2]:ans = max(ans, 2 + dfs(v1, v2, status))return ansans = 1for u in graph.keys():for v in graph[u]:if label[u] == label[v]:ans = max(ans, dfs(u, v, 0))m = len(graph[u])for i in range(m-1):for j in range(i+1, m):v, w = graph[u][i], graph[u][j]if label[v] == label[w]:ans = max(ans, 1+dfs(v, w, 1<<u))return ans

提交代码评测得到：耗时8934ms，占用内存207.40MB。