【算法】Longest Palindromic Substring

发表于 | 分类于 | 阅读次数:

最近刷LeetCode遇到一个比较有意思的题目（Longest Palindromic Substring），求一个字符串的最大回文子串。题目本身并不难，但需要理清思路才好理解，借此文记录下。

题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

给定一个字符串，找出其最长的回文子串。你可假定字符串长度最大不超过1000。

官方题目链接

什么是最长回文子串？

一个正反顺序打印输出结果相等的字符串。左右字符具备对称性。

举例： “aabbaa” 、 “bbcbb”、”bccb” 等等。

怎么处理字符串长度奇偶情况

  • 各字符间插入特殊字符。比如插入：#
  • 从相邻两个字符开始比较。

我的解法

大概说下思路：

  1. 原字符间插入特殊字符（#），处理长度为偶数情况；
  2. 循环遍历每个字符算出其最大回文子串的长度；
  3. 再剔除得到的回文子串中的特殊字符（#）；

Java 代码实现

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
45
46
47
48
49
50
51
52
53
54
public String longestPalindrome(String s) {
if (s == null || s.length() <= 1) {
   	return s;
}
//插入 # 解决偶数对称字符
s = insertSpecialChar(s, '#');
final int length = s.length();
// 最大回文子串长度
int maxLen = 0;
int[] longestIndex = new int[2];
int i = 0, j = 0;
for (int index = 1; index < length; index++) {
   	i = index - 1;
   	j = index + 1;
   	while ((i >= 0 && j <= length - 1) && (s.charAt(i) == s.charAt(j))) {
       	i--;
       	j++;
   	}
   	if (maxLen < (j - i - 1)) {
       	maxLen = j - i - 1;
       	longestIndex[0] = i + 1;
       	longestIndex[1] = j;//substring 方法 endIndex 可以等于length 。取值范围是[startIndex, endIndex)
   	}
}
final String longestPalindromeStr = s.substring(longestIndex[0], longestIndex[1]);
return deleteSpecialChar(longestPalindromeStr, '#'));
}
  // 插入特殊字符
  private String insertSpecialChar(String s, char specialChar) {
       StringBuilder sBuilder = new StringBuilder();
       for (int i = 0; i < s.length(); i++) {
           sBuilder.append(specialChar + String.valueOf(s.charAt(i)));
       }
       sBuilder.append(specialChar);
       return sBuilder.toString();
   }
  //剔除
  private String deleteSpecialChar(String s, char specialChar) {
      StringBuilder stringBuilder = new StringBuilder();
      for (int i = 0; i < s.length(); i++) {
          if (specialChar != s.charAt(i)) {
              stringBuilder.append(String.valueOf(s.charAt(i)));
          }
      }
      return stringBuilder.toString();
   }

这个解法思路比较简单，按照官方说法这就是蛮力解决方案（brute force solution）。效率缺陷就在于检查后面字符的回文子串时有可能前面已经比较过的字符又得重复比较一次。

官方推荐解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public String longestPalindrome(String s) {
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}

思路还是比较清晰，但未使用字符间插入特殊字符，而循环比较i和i 、i和i+1（也就是处理最大回文字符长度为偶数的情况，相邻的两个数相等）。较上一种解法少了插入和剔除特殊字符的操作，但每次遍历都多一次i和i+1的比较，按照正常理解如果字符串太长，此方法应该会耗时更多才对；于是我做了个测试，同样的字符串（长度约为1w)，实际测试下来，此解法较上一种执行反而更快。我猜原因应该是：插入和剔除特殊字符操作耗时、插入后字符长度翻倍、比较逻辑简单三个原因导致。有其它见解的同学请留言解惑，谢谢。

官方推荐解法2

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
45
46
47
public String longestPalindromeOfficialSn(String s) {
      if (s == null || s.length() <= 1) {
          return s;
      }
       //插入 # 解决偶数对称字符
      final String temp = insertSpecialChar(s, '#');
      final int length = temp.length();
      int centerIndex = 0, rightIndex = 0;
      final int[] p = new int[length];
      for (int i = 0; i < length; i++) {
          // iMirror 为 i 的对称点
          int iMirror = 2 * centerIndex - i;
          int pMirror = (iMirror < 0) ? 0 : p[iMirror];
          p[i] = (rightIndex > i) ? Math.min(pMirror, rightIndex - i) : 0;
          int L = i - 1 - p[i];
          int R = i + 1 + p[i];
          while (L >= 0 && R < length && temp.charAt(L) == temp.charAt(R)) {
              p[i]++;
              L = i - 1 - p[i];
              R = i + 1 + p[i];
          }
          if (i + p[i] > rightIndex) {
              // 右移已算出的回文子串
              rightIndex = i + p[i];
              centerIndex = i;
          }
      }
      // 找出最大回文子串: 数组中最大的数
      int maxLength = 0, index = 0;
      for (int j = 0; j < length; j++) {
          if (maxLength < p[j]) {
              maxLength = p[j];
              index = j;
          }
      }
      String ret = temp.substring(index - maxLength, index + maxLength);
      System.out.println( "index = "+index+" maxLength "+maxLength);
      return s.substring((index - maxLength)/2, (index + maxLength)/2);
  }

此解法最大优势就是利用回文子串的对称性，避免重复比较，提高执行效率；也省去了剔除特殊字符的过程。

要想理解此解法关键要看懂这两句代码

1
2
int iMirror = 2 * centerIndex - i;
p[i] = (rightIndex > i) ? Math.min(pMirror, rightIndex - i) : 0;
  1. 变量含义：i 和 iMirror 表示字符串中两个字符索引，centerIndex 是其对称点索引。p[i]表示以i索引的字符为中心的左右对称字符对数。rightIndex 则是以centerIndex点字符的最大回文子串的最右边索引位置。
  2. 由于对称性，iMirror 为 i 的对称点不难得出 iMirror = centerIndex - (i - centerIndex)，即代码中的 int iMirror = 2 * centerIndex - i;
  3. 当前点i + 对称点iMirror的p[iMirror] 如果小于rightIndex则可得出p[i] = p[iMirror]，看下面代码： 
1
2
3
4
5
6
7
8
9
if(i + p[iMirror] < rightIndex){
   p[i] = p[iMirror];
}else{
  p[iMirror] >= rightIndex - i;
  //根据p[centerIndex]的回文子串对称性可知，p[i]>=rightIndex - i; 超过rightIndex为未知情况，所以去最小值p[i] = rightIndex - i;
}
// 所以就得出了下面这句代码。其中i>=rightIndex的情况未比较过的字符，所以默认赋值0
p[i] = (rightIndex > i) ? Math.min(pMirror, rightIndex - i) : 0;

此算法重点在于理解对称性，避免重复比较。欲知详情请查阅参考文章。

参考

其它

说下文章标题中的 DSAA ，其实就是数据结构与算法（Data Structures And Algorithms）的英文字母缩写，这样命名主要是想写一个系列文章来分享和记录我的算法学习过程，与君共勉。代码托管在github，欢迎star。

0%