AlgorithmAndLeetCode · pull · Jul 13, 2025 · Jul 13, 2025 · Jul 13, 2025 · Jul 13, 2025
diff --git a/DFS/3615.Longest-Palindromic-Path-in-Graph/3615.Longest-Palindromic-Path-in-Graph.cpp b/DFS/3615.Longest-Palindromic-Path-in-Graph/3615.Longest-Palindromic-Path-in-Graph.cpp
@@ -0,0 +1,46 @@
+class Solution {
+    vector<int>adj[14];
+    int memo[14][14][1<<14];
+    string label;
+public:
+    int dfs(int u, int v, int mask) {        
+        if (memo[u][v][mask]!=-1) return memo[u][v][mask];
+        int ret = 0;
+        for (int u2: adj[u]) {
+            if (mask&(1<<u2)) continue;
+            for (int v2: adj[v]) {
+                if (u2==v2) continue;
+                if (mask&(1<<v2)) continue;
+                if (label[u2]!=label[v2]) continue;
+                int newMask = mask | (1<<u2) | (1<<v2);
+                ret = max(ret, 2+dfs(u2,v2, newMask));
+            }            
+        }
+        memo[u][v][mask] = ret;
+        return ret;        
+    }
+    int maxLen(int n, vector<vector<int>>& edges, string label) {
+        this->label = label;
+        for (auto& e: edges) {
+            adj[e[0]].push_back(e[1]);
+            adj[e[1]].push_back(e[0]);
+        }
+        memset(memo, -1, sizeof(memo));
+
+        int ret = 1;
+        for (int u=0; u<n; u++) {            
+            int mask = 1<<u;            
+            ret = max(ret, 1+dfs(u,u, mask));
+        }
+
+        for (int u=0; u<n; u++) 
+            for (int v: adj[u]) {
+                if (u<v && label[u]==label[v]) {                    
+                    int mask = (1<<u) | (1<<v);
+                    ret = max(ret, 2+dfs(u,v, mask));
+                }
+            }
+
+        return ret;
+    }
+};
diff --git a/DFS/3615.Longest-Palindromic-Path-in-Graph/Readme.md b/DFS/3615.Longest-Palindromic-Path-in-Graph/Readme.md
@@ -0,0 +1,9 @@
+### 3615.Longest-Palindromic-Path-in-Graph
+
+考虑到本题的规模很小`n<=14`，我们可以考虑穷举回文路径的构造。
+
+首先考虑长度为奇数的路径。我们可以从任意一个节点作为中间元素，不断往两边添加对称字符的节点。因此我们需要记录路径最两端的节点编号u和v。每个回合，对于已知的回文路径(u,v)，我们找u的所有邻接节点u2，v的所有邻接节点v2，如果恰好u2和v2的字符相同，那么我们就可以将回文路径扩展成为(u2,v2)，同时路径长度增2. 为了提高搜索效率和避免同一个节点被多次使用，我们可以用bit mask记录该路径已经用过了哪些节点，来避免重复的状态。
+
+另一种情况是考虑长度为偶数的路径。初始状态时，我们需要遍历所有相邻的节点u和v，如果他们的字符相同，那么就可以从(u,v)开始，做与之前一样的递归搜索。
+
+第二种情况耗时更多一些。总的时间复杂度是`o(n^2)*(2^n)`。
diff --git a/Readme.md b/Readme.md
@@ -585,6 +585,7 @@
 [2741.Special-Permutations](https://github.com/wisdompeak/LeetCode/tree/master/DFS/2741.Special-Permutations) (M+)      
 [2746.Decremental-String-Concatenation](https://github.com/wisdompeak/LeetCode/tree/master/DFS/2746.Decremental-String-Concatenation) (H-)      
 [3213.Construct-String-with-Minimum-Cost](https://github.com/wisdompeak/LeetCode/tree/master/DFS/3213.Construct-String-with-Minimum-Cost) (H-)      
+[3615.Longest-Palindromic-Path-in-Graph](https://github.com/wisdompeak/LeetCode/tree/master/DFS/3615.Longest-Palindromic-Path-in-Graph) (H-)      
 * ``hidden matrix``    
 [489.Robot-Room-Cleaner](https://github.com/wisdompeak/LeetCode/blob/master/DFS/489.Robot-Room-Cleaner) (H)   
 [1778.Shortest-Path-in-a-Hidden-Grid](https://github.com/wisdompeak/LeetCode/tree/master/DFS/1778.Shortest-Path-in-a-Hidden-Grid) (H-)