分割回文串图解

问题描述

给定一个字符串 s，将 s 分割成若干子串，使每个子串都是回文串。返回所有可能的分割方案。

示例

输入："aab"
输出：

[
  ["a","a","b"],
  ["aa","b"]
]

算法思路：回溯法

核心思想

1. 逐步构建：从左到右逐步构建回文子串
2. 回溯尝试：对每个位置尝试所有可能的回文分割
3. 剪枝优化：提前终止不可能产生回文的分支

关键步骤

1. 从字符串起始位置开始
2. 寻找所有以当前位置开头的回文子串
3. 对每个回文子串，递归处理剩余部分
4. 到达字符串末尾时保存有效分割

JavaScript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

function partition(s) {
    const result = [];
    
    // 判断是否是回文
	// str: s字符串, left:左index, right:右index
    function isPalindrome(str, left, right) {
        while (left < right) {
            if (str[left++] !== str[right--]) return false;
        }
        return true;
    }
    
    // 回溯函数	
	//start：当前处理位置的起始索引, path：当前已选择的回文子串列表
	function backtrack(start, path) {
    	// 终止条件：已经处理完整个字符串
    	if (start === s.length) {
        	result.push([...path]);
        	return;
    	}	
    
    	// 尝试所有可能的分割点
    	for (let end = start; end < s.length; end++) {
        	// 检查当前子串是否是回文
        	if (isPalindrome(s, start, end)) {
            	// 如果是回文，加入当前路径
            	path.push(s.substring(start, end + 1));
            	// 递归处理剩余部分
            	backtrack(end + 1, path);
            	// 回溯，移除最后的选择
            	path.pop();
        	}
    	}
	}
    
    backtrack(0, []);
    return result;
}

我将用更直观的图解方式，配合分步拆解，帮助你完全理解这个回溯过程。让我们以 s = "aab" 为例，用动画式的图解来说明。

初始状态

字符串: a a b
索引:  0 1 2
当前路径: []
待处理: 全部(0-2)

第一步：处理位置0

尝试所有以位置0开头的子串

选择1：取”a” (0-0)

1. 检查回文：”a”是回文
2. 更新路径：["a"]
3. 递归处理剩余：”ab” (从位置1开始)

当前路径: ["a"]
剩余字符串: a b (索引1-2)

子递归：处理位置1

尝试所有以位置1开头的子串

选择1.1：取”a” (1-1)

1. 检查回文：”a”是回文
2. 更新路径：["a", "a"]
3. 递归处理剩余：”b” (从位置2开始)

当前路径: ["a", "a"]
剩余字符串: b (索引2)

子子递归：处理位置2

尝试所有以位置2开头的子串

选择1.1.1：取”b” (2-2)

1. 检查回文：”b”是回文
2. 更新路径：["a", "a", "b"]
3. 到达字符串末尾 → 保存结果 ["a","a","b"]
4. 回溯：移除”b” → 路径回退到 ["a","a"]

选择1.2：取”ab” (1-2)

1. 检查回文：”ab”不是回文 → 跳过

子递归结束

回溯：移除”a” → 路径回退到 ["a"]

选择2：取”aa” (0-1)

1. 检查回文：”aa”是回文
2. 更新路径：["aa"]
3. 递归处理剩余：”b” (从位置2开始)

当前路径: ["aa"]
剩余字符串: b (索引2)

子递归：处理位置2

尝试所有以位置2开头的子串

选择2.1：取”b” (2-2)

1. 检查回文：”b”是回文
2. 更新路径：["aa", "b"]
3. 到达字符串末尾 → 保存结果 ["aa","b"]
4. 回溯：移除”b” → 路径回退到 ["aa"]

选择3：取”aab” (0-2)

1. 检查回文：”aab”不是回文 → 跳过

最终结果

[
  ["a","a","b"],
  ["aa","b"]
]

关键过程图解

backTrack(0, [])
│
├─ end=0: 取 "a" (s[0..0])
│  ├─ backTrack(1, ["a"])
│  │  ├─ end=1: 取 "a" (s[1..1]) → path=["a","a"]
│  │  │  ├─ backTrack(2, ["a","a"])
│  │  │  │  ├─ end=2: 取 "b" (s[2..2]) → path=["a","a","b"] → 保存结果
│  │  │  │  └─ end++ → 循环结束
│  │  │  └─ path.pop() → ["a"]
│  │  │
│  │  └─ end=2: 检查 "ab" (s[1..2]) → 不是回文，跳过
│  └─ path.pop() → []
│
└─ end=1: 取 "aa" (s[0..1]) → path=["aa"]
└─ backTrack(2, ["aa"])
    └─ end=2: 取 "b" (s[2..2]) → path=["aa","b"] → 保存结果

为什么这样能保证不遗漏？

1. 系统性尝试：对每个位置，尝试所有可能的子串长度
2. 回文剪枝：只有回文子串才会继续递归
3. 回溯保证：每次递归后恢复状态，确保其他分支能正确执行

常见疑问解答

Q1：为什么要在path.push后立即pop？
A：这是回溯算法的核心——在递归返回后撤销选择，确保：

• 上层递归的path不受下层影响
• 可以尝试其他分割方式

Q2：如何避免重复计算回文？
A：可以用动态规划预处理回文信息：

1
2

// dp[i][j]表示s[i..j]是否是回文
const dp = Array(n).fill().map(() => Array(n).fill(false));

Q3：时间复杂度为什么是O(n*2^n)？

• 最坏情况（如”aaaa”）有2^(n-1)种分割方式
• 每次判断回文需要O(n)时间

通过这种”尝试-递归-回溯”的流程，系统性地探索了所有可能的回文分割方案。关键是要理解递归树如何展开，以及回溯如何保证状态重置。

复杂度分析

• 时间复杂度：O(n * 2^n)
  • 最坏情况下有 2^n 种分割方式
  • 每次判断回文需要 O(n) 时间
• 空间复杂度：O(n)
  • 递归栈深度最多为 n

优化方法

1. 动态规划预处理

预先计算所有子串是否为回文，存储为二维数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function partition(s) {
    const n = s.length;
    const dp = Array(n).fill().map(() => Array(n).fill(false));
    const result = [];
    
    // 预处理回文信息
    for (let i = n - 1; i >= 0; i--) {
        for (let j = i; j < n; j++) {
            dp[i][j] = (s[i] === s[j]) && (j - i <= 2 || dp[i+1][j-1]);
        }
    }
    
    // 回溯函数（同上）
    // ...
}

2. 记忆化搜索

缓存已计算的回文判断结果，避免重复计算。

常见问题解答

Q1：为什么需要回溯？
A：回溯法可以系统地探索所有可能的分割方式，当某条路径无法继续时回退尝试其他选择。

Q2：如何处理空字符串？
A：空字符串本身被视为有效输入，返回包含空列表的列表 [[]]。

Q3：如何避免重复计算回文？
A：使用动态规划预处理或记忆化技术存储已计算的回文判断结果。

实际应用场景

1. 文本分词处理
2. DNA序列分析
3. 数据压缩算法
4. 密码学中的字符串分解

通过这种回溯+剪枝的方法，我们可以高效地找出所有可能的回文分割方案。理解递归树的构建过程是掌握此类问题的关键。

环形链表

检测链表是否有环（快慢指针法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14

function hasCycle(head) {
  if (!head || !head.next) return false;
  
  let slow = head;
  let fast = head.next;
  
  while (fast && fast.next) {
    if (slow === fast) return true;
    slow = slow.next;
    fast = fast.next.next;
  }
  
  return false;
}

找到环的起始节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

function detectCycleStart(head) {
  if (!head || !head.next) return null;
  
  let slow = head;
  let fast = head;
  let hasCycle = false;
  
  // 检测是否有环
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    
    if (slow === fast) {
      hasCycle = true;
      break;
    }
  }
  
  if (!hasCycle) return null;
  
  // 找到环的起点
  slow = head;
  while (slow !== fast) {
    slow = slow.next;
    fast = fast.next;
  }
  
  return slow;
}

实际应用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// 创建环形链表
const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);
const node4 = new Node(4);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2; // 形成环

// 检测环
console.log('Has cycle:', hasCycle(node1)); // true
console.log('Cycle starts at:', detectCycleStart(node1).data); // 2

环形链表在需要循环访问数据的场景中非常有用，如音乐播放列表、轮播图、资源轮询等。

环形链表检测算法详细解析

这段代码是用来检测链表中是否存在环，并找到环的起始节点的经典算法。它使用了”快慢指针”（Floyd’s Cycle-Finding Algorithm）的方法。下面我将详细解析每一部分的作用和原理。

算法整体思路

1. 检测是否有环：使用快慢指针遍历链表，如果快指针追上慢指针，则存在环
2. 找到环的起点：重置一个指针到链表头，然后两个指针同步前进，相遇点即为环的起点

代码逐行解析

第一部分：初始检查

1

if (!head || !head.next) return null;

• 检查链表是否为空或只有一个节点
• 这两种情况都不可能形成环，直接返回null

第二部分：初始化指针

1
2
3

let slow = head;
let fast = head;
let hasCycle = false;

• slow 慢指针，每次前进一步
• fast 快指针，每次前进两步
• hasCycle 标记是否检测到环

第三部分：检测环的存在

1
2
3
4
5
6
7
8
9

while (fast && fast.next) {
  slow = slow.next;
  fast = fast.next.next;
  
  if (slow === fast) {
    hasCycle = true;
    break;
  }
}

• 循环条件：快指针及其下一个节点不为null（防止空指针异常）
• 慢指针前进一步，快指针前进两步
• 如果快慢指针相遇，说明存在环，设置标记并退出循环

第四部分：无环处理

1

if (!hasCycle) return null;

• 如果没有检测到环，直接返回null

第五部分：寻找环的起点

1
2
3
4
5
6

slow = head;
while (slow !== fast) {
  slow = slow.next;
  fast = fast.next;
}
return slow;

• 将慢指针重置到链表头部
• 快慢指针现在都每次前进一步
• 当它们再次相遇时，相遇点就是环的起点
• 返回这个节点

为什么这个算法有效？

数学原理

设：

• 链表非环部分长度为 L
• 环的长度为 C
• 快慢指针第一次相遇时，慢指针走了 S 步，快指针走了 2S 步

当快慢指针第一次相遇时：

1. 快指针比慢指针多走了 n 圈环：2S = S + nC ⇒ S = nC
2. 慢指针走的步数可以表示为：S = L + a（a 是环内位置）

由 L + a = nC ⇒ L = nC - a

这意味着：从链表头到环起点的距离 L，等于从相遇点继续走 nC - a 步。这正是为什么第二次遍历时，从链表头和相遇点同时出发的两个指针会在环起点相遇。

为什么第二次遍历能找到起点？

1. 第一次相遇后，将慢指针重置到头部
2. 两个指针现在都每次走一步
3. 当慢指针走了 L 步到达环起点时：
   • 快指针从相遇点走了 L 步
   • 因为 L = nC - a，所以快指针的位置是：a (原位置) + L = a + nC - a = nC
   • 即快指针也回到了环起点

时间复杂度分析

• 检测环：O(n) - 最多遍历整个链表一次
• 寻找起点：O(n) - 最多再遍历一次
• 总时间复杂度：O(n)

空间复杂度：O(1)，只使用了固定数量的指针

示例演示

考虑链表：1 → 2 → 3 → 4 → 5 → 2（指向节点2形成环）

1. 第一次遍历：

   • 慢指针路径：1 → 2 → 3 → 4
   • 快指针路径：1 → 3 → 5 → 3 → 5 → …
   • 在节点4相遇

2. 第二次遍历：

   • 慢指针从头开始：1 → 2
   • 快指针从4开始：4 → 5 → 2
   • 在节点2相遇，这就是环的起点

这个算法巧妙利用了数学关系，通过两次遍历就能准确找到环的起点，是解决环形链表问题的经典方法。