Go 语言实现回文字符串检测算法详解

• 若字符相同，left++，right--
• 若字符不同，返回 false
• 若交叉结束，返回 true

4. Go 语言字符串处理关键点

Go 中字符串是 UTF-8 编码，本质是 byte 切片，中文占多个字节。

⚠ 注意：若直接使用 s[i]，可能截断中文字符。

正确做法：转换为 []rune，使用 rune 切片处理。

5. Unicode 与 rune

Go 中：

• byte：1 字节
• rune：int32，表示一个 Unicode 字符

例如："中" 占 3 个 byte，但只占 1 个 rune。

四、实现思路

我们将实现三种版本：

第一种：基础双指针版本

步骤：

1. 转为 rune 切片
2. 定义 left=0, right=len-1
3. 比较 r[left] 与 r[right]
4. 不等返回 false
5. 相等则移动指针
6. 循环结束返回 true

第二种：忽略大小写与非字母字符版本

步骤：

1. 预处理字符串
2. 转小写
3. 过滤非字母数字字符
4. 再使用双指针判断

第三种：递归实现版本

递归思想：

• 若首尾不同 → false
• 若字符串长度 ≤1 → true
• 否则递归中间部分

五、完整实现代码

// ============================================
// 文件：main.go
// ============================================
package main

import (
	"fmt"
	"strings"
	"unicode"
)

// ============================================
// 方法一：基础双指针版本（支持 Unicode）
// ============================================
// IsPalindromeBasic 判断字符串是否为回文（区分大小写）
// 时间复杂度：O(n)
// 空间复杂度：O(n)（因转换为 rune）
func IsPalindromeBasic(s string) bool {
	// 转换为 rune 切片，防止中文字符被截断
	runes := []rune(s)
	// 定义双指针
	left := 0
	right := len(runes) - 1
	// 循环判断
	for left < right {
		// 若不相等，直接返回 false
		if runes[left] != runes[right] {
			return false
		}
		// 指针移动
		left++
		right--
	}
	return true
}

// ============================================
// 方法二：忽略大小写与非字母数字字符
// ============================================
// IsPalindromeAdvanced 忽略大小写与特殊字符
func IsPalindromeAdvanced(s string) bool {
	// 统一转小写
	s = strings.ToLower(s)
	// 过滤非字母数字字符
	var filtered []rune
	for _, r := range s {
		if unicode.IsLetter(r) || unicode.IsDigit(r) {
			filtered = append(filtered, r)
		}
	}
	// 双指针判断
	left := 0
	right := len(filtered) - 1
	for left < right {
		if filtered[left] != filtered[right] {
			return false
		}
		left++
		right--
	}
	return true
}

// ============================================
// 方法三：递归实现
// ============================================
// IsPalindromeRecursive 递归判断
func IsPalindromeRecursive(s string) bool {
	runes := []rune(s)
	return recursiveCheck(runes, 0, len(runes)-1)
}

// 递归核心函数
func recursiveCheck(runes []rune, left int, right int) bool {
	// 终止条件：指针交叉
	if left >= right {
		return true
	}
	// 若不相等，返回 false
	if runes[left] != runes[right] {
		return false
	}
	// 递归检查中间部分
	return recursiveCheck(runes, left+1, right-1)
}

// ============================================
// 主函数测试
// ============================================
func main() {
	testCases := []string{
		"abba",
		"Madam",
		"A man, a plan, a canal: Panama",
		"hello",
		"上海自来水来自海上",
	}
	fmt.Println("====== 基础版本测试 ======")
	for _, str := range testCases {
		fmt.Printf("%s 是否回文：%v\n", str, IsPalindromeBasic(str))
	}
	fmt.Println("\n====== 高级版本测试（忽略大小写和符号） ======")
	for _, str := range testCases {
		fmt.Printf("%s 是否回文：%v\n", str, IsPalindromeAdvanced(str))
	}
	fmt.Println("\n====== 递归版本测试 ======")
	for _, str := range testCases {
		fmt.Printf("%s 是否回文：%v\n", str, IsPalindromeRecursive(str))
	}
}

六、代码详细解读

1. IsPalindromeBasic

作用：

• 使用双指针判断是否回文
• 支持 Unicode 字符
• 区分大小写
• 不忽略特殊字符

适合基础算法练习。

2. IsPalindromeAdvanced

作用：

• 忽略大小写
• 忽略标点符号
• 忽略空格
• 适合真实工程场景

核心点：

• 使用 unicode.IsLetter 判断字符类型
• 使用 strings.ToLower 统一大小写

3. IsPalindromeRecursive

作用：

• 使用递归实现回文判断
• 教学意义大于工程意义
• 不推荐在大数据场景使用（栈空间开销）

4. recursiveCheck

作用：

• 执行递归核心逻辑
• 每次向内缩进一层

七、项目总结

本项目系统实现了回文字符串判断的三种方式，并详细讲解了算法原理。

我们掌握了：

• 双指针算法思想
• Unicode 安全处理
• Go 字符串底层机制
• 递归与迭代对比
• 实际工程中字符串预处理技巧

双指针法是最优选择：

• 时间复杂度 O(n)
• 空间复杂度 O(1)（若原地处理）

八、常见问题及解答

Q1：为什么要转为 rune？

因为 Go 字符串默认是 byte 切片，中文字符会被拆分。

Q2：如何做到 O(1) 空间？

可以直接双指针在原字符串上用 range 处理，但实现复杂。

Q3：递归会不会栈溢出？

大字符串可能导致栈溢出，不推荐生产环境使用。

Q4：能否支持 emoji？

可以，只要转为 rune 处理即可。

九、扩展方向与性能优化

1. 最大回文子串问题

可学习：

• 中心扩展法
• Manacher 算法（O(n)）

2. 流式数据回文检测

使用 rolling hash 实现。

3. 并发版本

大规模文本分片处理。

4. 性能优化

• 减少内存分配
• 原地过滤
• 使用 sync.Pool