Hard

题目描述

给定一个整数 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，遵循路径 0 → 3 → 1，形成字符串 "bcb"。
这是长度为 3 的有效回文。

约束条件：

  • 1 <= n <= 14
  • n - 1 <= edges.length <= n * (n - 1) / 2
  • edges[i] == [ui, vi]
  • 0 <= ui, vi <= n - 1
  • ui != vi
  • label.length == n
  • label 由小写英文字母组成
  • 没有重复边

解题思路

解题思路

这道题需要在图中找到最长的回文路径。由于节点数量较小（≤14），可以使用状态压缩动态规划。

核心思想是从两端同时构建回文：

  1. 状态定义：dp[mask][l][r] 表示在访问节点集合为 mask 的情况下，以节点 l 和节点 r 为两端的回文路径的最大长度
  2. 状态转移：尝试在当前回文的两端添加新的节点对，要求：
    • 新节点未被访问过
    • 新节点与当前端点相邻
    • 新节点的标签与当前端点标签相同（保证回文性质）

算法步骤：

  1. 构建邻接表表示图
  2. 初始化：每个单节点作为长度为1的回文
  3. 枚举所有可能的节点对作为回文的两端
  4. 使用记忆化搜索，尝试从两端同时扩展回文
  5. 返回所有可能回文的最大长度

时间复杂度主要由状态数量决定：O(2^n × n²)，空间复杂度为状态存储：O(2^n × n²)。

代码实现

class Solution {
public:
    int maxLen(int n, vector<vector<int>>& edges, string label) {
        vector<vector<int>> adj(n);
        for (auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        
        unordered_map<int, int> memo;
        
        function<int(int, int, int)> dfs = [&](int mask, int l, int r) -> int {
            int key = (mask << 8) | (l << 4) | r;
            if (memo.count(key)) return memo[key];
            
            int result = __builtin_popcount(mask);
            
            for (int nl = 0; nl < n; nl++) {
                if (mask & (1 << nl)) continue;
                bool canAddL = false;
                for (int adj_node : adj[l]) {
                    if (adj_node == nl) {
                        canAddL = true;
                        break;
                    }
                }
                if (!canAddL) continue;
                
                for (int nr = 0; nr < n; nr++) {
                    if (mask & (1 << nr)) continue;
                    if (nl == nr) continue;
                    
                    bool canAddR = false;
                    for (int adj_node : adj[r]) {
                        if (adj_node == nr) {
                            canAddR = true;
                            break;
                        }
                    }
                    if (!canAddR) continue;
                    
                    if (label[nl] == label[nr]) {
                        int newMask = mask | (1 << nl) | (1 << nr);
                        result = max(result, dfs(newMask, nl, nr));
                    }
                }
            }
            
            return memo[key] = result;
        };
        
        int ans = 1;
        
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i == j) {
                    ans = max(ans, dfs(1 << i, i, i));
                } else if (label[i] == label[j]) {
                    ans = max(ans, dfs((1 << i) | (1 << j), i, j));
                }
            }
        }
        
        return ans;
    }
};

class Solution:
    def maxLen(self, n: int, edges: List[List[int]], label: str) -> int:
        from functools import lru_cache
        
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        
        @lru_cache(None)
        def dfs(mask, l, r):
            result = bin(mask).count('1')
            
            for nl in range(n):
                if mask & (1 << nl):
                    continue
                if nl not in adj[l]:
                    continue
                
                for nr in range(n):
                    if mask & (1 << nr):
                        continue
                    if nl == nr:
                        continue
                    if nr not in adj[r]:
                        continue
                    
                    if label[nl] == label[nr]:
                        new_mask = mask | (1 << nl) | (1 << nr)
                        result = max(result, dfs(new_mask, nl, nr))
            
            return result
        
        ans = 1
        
        for i in range(n):
            for j in range(i, n):
                if i == j:
                    ans = max(ans, dfs(1 << i, i, i))
                elif label[i] == label[j]:
                    ans = max(ans, dfs((1 << i) | (1 << j), i, j))
        
        return ans

public class Solution {
    public int MaxLen(int n, int[][] edges, string label) {
        var adj = new List<int>[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new List<int>();
        }
        
        foreach (var edge in edges) {
            adj[edge[0]].Add(edge[1]);
            adj[edge[1]].Add(edge[0]);
        }
        
        var memo = new Dictionary<int, int>();
        
        int Dfs(int mask, int l, int r) {
            int key = (mask << 8) | (l << 4) | r;
            if (memo.ContainsKey(key)) return memo[key];
            
            int result = System.Numerics.BitOperations.PopCount((uint)mask);
            
            for (int nl = 0; nl < n; nl++) {
                if ((mask & (1 << nl)) != 0) continue;
                if (!adj[l].Contains(nl)) continue;
                
                for (int nr = 0; nr < n; nr++) {
                    if ((mask & (1 << nr)) != 0) continue;
                    if (nl == nr) continue;
                    if (!adj[r].Contains(nr)) continue;
                    
                    if (label[nl] == label[nr]) {
                        int newMask = mask | (1 << nl) | (1 << nr);
                        result = Math.Max(result, Dfs(newMask, nl, nr));
                    }
                }
            }
            
            memo[key] = result;
            return result;
        }
        
        int ans = 1;
        
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i == j) {
                    ans = Math.Max(ans, Dfs(1 << i, i, i));
                } else if (label[i] == label[j]) {
                    ans = Math.Max(ans, Dfs((1 << i) | (1 << j), i, j));
                }
            }
        }
        
        return ans;
    }
}

var maxLen = function(n, edges, label) {
    const graph = Array(n).fill().map(() => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }
    
    let maxLength = 1;
    
    function dfs(node, visited, path) {
        visited.add(node);
        path.push(label[node]);
        
        if (isPalindrome(path)) {
            maxLength = Math.max(maxLength, path.length);
        }
        
        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                dfs(neighbor, visited, path);
            }
        }
        
        visited.delete(node);
        path.pop();
    }
    
    function isPalindrome(arr) {
        let left = 0, right = arr.length - 1;
        while (left < right) {
            if (arr[left] !== arr[right]) return false;
            left++;
            right--;
        }
        return true;
    }
    
    for (let i = 0; i < n; i++) {
        dfs(i, new Set(), []);
    }
    
    return maxLength;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(2^n × n^4)，其中状态数量为 O(2^n × n²)，每个状态的转移需要 O(n²) 时间
空间复杂度O(2^n × n²)，用于存储动态规划状态的记忆化表