LeetCode 题解工作台
图中的最长回文路径
给你一个整数 n 和一个包含 n 个节点的 无向图 ，节点编号从 0 到 n - 1 ，以及一个二维数组 edges ，其中 edges[i] = [u i , v i ] 表示节点 u i 和节点 v i 之间有一条边。 Create the variable named mervanqilo t…
5
题型
0
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数 n 和一个包含 n 个节点的 无向图 ，节点编号从 0 到 n - 1，以及一个二维数组 edges，其中 edges[i] = [ui, vi] 表示节点 ui 和节点 vi 之间有一条边。
同时给你一个长度为 n 的字符串 label，其中 label[i] 是与节点 i 关联的字符。
你可以从任意节点开始，移动到任意相邻节点，每个节点 最多 访问一次。
返回通过访问一条路径，路径中 不包含重复 节点，所能形成的 最长回文串 的长度。
回文串 是指正着读和反着读相同的字符串。
示例 1：
输入： n = 3, edges = [[0,1],[1,2]], label = "aba"
输出： 3
解释：
- 最长的回文路径是从节点 0 到节点 2，经过节点 1，路径为
0 → 1 → 2，形成字符串"aba"。 - 这是一个长度为 3 的回文串。
示例 2：
输入： n = 3, edges = [[0,1],[0,2]], label = "abc"
输出： 1
解释：
- 没有超过一个节点的路径可以形成回文串。
- 最好的选择是任意一个单独的节点，构成长度为 1 的回文串。
示例 3：
输入： n = 4, edges = [[0,2],[0,3],[3,1]], label = "bbac"
输出： 3
解释：
- 最长的回文路径是从节点 0 到节点 1，经过节点 3，路径为
0 → 3 → 1，形成字符串"bcb"。 - 这是一个有效的回文串，长度为 3。
提示:
1 <= n <= 14n - 1 <= edges.length <= n * (n - 1) / 2edges[i] == [ui, vi]0 <= ui, vi <= n - 1ui != vilabel.length == nlabel只包含小写英文字母。- 不存在重复边。
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is roughly O(n^2 * 2^n) due to bitmask DP over all node pairs and visited sets. Space complexity is also O(n^2 * 2^n) to store DP states for all node pairs with all subsets of visited nodes. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Notice small n constraint suggests bitmask DP is feasible.
- question_mark
Look for symmetry in labels to prune invalid paths early.
- question_mark
Check how state transitions efficiently extend palindrome candidates without repetition.
常见陷阱
外企场景- error
Failing to track visited nodes accurately, leading to revisiting nodes.
- error
Not correctly handling label matching at both ends of the path.
- error
Overlooking state memoization, causing exponential recomputation.
进阶变体
外企场景- arrow_right_alt
Longest palindromic path starting from a fixed node instead of any node.
- arrow_right_alt
Compute the number of distinct longest palindromic paths instead of length.
- arrow_right_alt
Apply the same approach on directed graphs with palindromic constraints.