寻找最长回文串

leetcode►substring 评论

寻找最长回文子串

难度： 中等
问题描述：
给你一个字符串 s，找到 s 中最长的回文子串。

示例 ：

1
2
输入：s = "babad"
输出："bab" 或者 “aba”
1
2
输入：s = "cbbd"
输出："bb"

链接：原题链接

解法

解法1： 中心扩散法
  • 思路：将字符串中的每个字符当做回文的中心，来计算以字符为中心的回文串长度，最终选取一个最长的回文串，即为最长回文串。
    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
    39
    40
    41
    42
    43
    44
    func longestPalindrome(s string) string {
    	strLen := len(s)
    	// 如果是空字符,直接返回
    	if strLen == 0 {
    		return ""
    	}
    	// 只要 s 非空，回文长度至少为1
    	longest := 1
    	start := 0
    	for i := 0; i < strLen-1; i++ {
    		// 回文中心的中间部位重复字符数，例如 s="zhaoooahb"，当i=3时，则 rereplicateNum=3,leftLength=2
    		replicateNum := 1
    		for j := i; j < strLen-1; j++ {
    			if s[j] == s[j+1] {
    				replicateNum ++
    				continue
    			}
    			break
    		}

    		leftLength := computeLongest(s, i, replicateNum)
    		// 回文长度 = 重复的中心字符 + 左右两边的长度之和
    		if longest < replicateNum +2*leftLength {
    			longest = replicateNum +  2*leftLength
    			start = i - leftLength
    		}
    	}

    	return s[start : start+longest]
    }

    // 计算 index 的右边有多少个与 s[index] 重复的字符数
    func computeLongest(s string, index int, replicate int) int {
    	steLen := len(s)
    	leftLength := 0
    	for i := 1; (0 <= index-i) && (index + replicate + i - 1 < steLen); i++ {
    		if s[index - i] == s[index + replicate + i -1]{
    			leftLength++
    			continue
    		}
    		break
    	}
    	return leftLength
    }

    时间复杂度：O(N^2)
    空间复杂度：O(1)

解法2: 动态规划
  • 思路：对于回文串 “abcba”，其子串 “bcb” 也是回文串，所以建立一个二维表格，表格的每个单元代表其是否为回文串。例如,对于 s = “ababcdsd”, T[2][3] = true ,表示 s[2:4]（即“bab”）字符串是否为回文串。
  • 动态规划的状态转移方程为：

    T[j][i] = T[j+1][i-1] && s[j] == s[i] （s[j] 是左边字符，s[i] 是右边字符, 即 j <= i）

  • 代码：
    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
    39
    40
    41
    42
    43
    44
    func longestPalindrome(s string) string {
    	// 构造动态规划的二维表格 table[][]
    	length := len(s)
    	table := make([][]int, length)
    	// 存放最长回文串的长度
    	longest := 1
    	// 存放最长回文串的起始位置
    	start := 0

    	// 首先把对角线置为 1
    	for i := 0; i < length; i++ {
    		table[i] = make([]int,length)
    		table[i][i] = 1
    	}
        
            // i 是行标，j 是列标
            // 填表的顺序：先填第1列，再填第2列 ... 再填最后一列；对于每一列，从下往上填
    	for i := 0; i < length; i++ {
    		for j := i - 1; j >= 0; j-- {
    			if j >= 0 {
                                    // i == j +1 的时候， T[j+1][i-1] 不存在，因此要特殊处理一下
    				if i == j +1 && s[j] == s[i] {
    					table[j][i] =1
    					if longest == 1 {
    						longest = 2
    						start = j
    					}
    					continue
    				}

    				if s[i] == s[j] && table[j+1][i-1] == 1 {
    					table[j][i] = 1
    					if i - j + 1 > longest {
    						longest = i - j + 1
    						start = j
    					}
    					continue
    				}
    				table[j][i] = 0
    			}
    		}
    	}
    	return s[start : start + longest]
    }

    时间复杂度：O(N^2)
    空间复杂度：O(N^2)

注：
中心扩散法的总体的执行效率是比较高（本人代码在 leetcode 的执行用时超过其他同学的 90.7%；内存消耗超过 71.2%）
动态规划 总体的执行效率较低，其核心思想是通过使用空间换时间,通过记录小的回文来确定大回文，以降低对回文的判定时间（执行用时超过 22.8%，内存消耗超过 5.9%）

极地东风Block Chain

Hyperledger Fabric Developer