Longest Palindromic Substring

发表于 | 分类于

Longest Palindromic Substring(最长的回文子串)

题目描述：

给定一个字符串，找到字符串中的最长回文子串。

解题思路：

本题的常见解法有三种。第一种是中心扩展的方法。在遍历字符串的过程，以当前字符串为中心向左右两侧扩展，扩展结束后判断子串的长度。需要注意的是：这种方法中有偶回文串和奇数回文串的区别，遍历的过程需要区别对待。aba奇回文子串，abba是偶回文子串。

代码如下：

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
class Solution {
public:
    string longestPalindrome(string s) {
        int max_length = 1;//记录最长串的长度
        string res = s.substr(0,1);//以第一个字母为初始值回文串
        int left = 0; //记录向左扩展的下标
        int right = 0;//记录向右扩展的下标
        
        for (int i = 0; i < s.size(); i++){
            left = i;
            right = i;
            while((left >= 0) && (right < s.size()) && (s[left] == s[right])){
                left--;
                right++;
            }
            //判断奇回文串；如果下标满足要求并且左右相等的情况，左右扩展
            
            if ((right - left - 1) > max_length){
                max_length = right - left - 1;
                res = s.substr(left + 1, max_length);
            }//如果比当前长度长，改变长度和返回值
        }
        for (int i = 0; i < s.size() - 1; i++){
            if (s[i] == s[i + 1]){
                left = i - 1;
                right = i + 2;
            }else{
                continue;
            }//如果没有连续的两个字母相等，则当前遍历不可能是偶回文串
            
            while((left >= 0) && (right < s.size()) && (s[left] == s[right])){
                left--;
                right++;
            }
            //符合条件则左右扩展
            if ((right - left - 1) > max_length){
                max_length = right - left - 1;
                res = s.substr(left + 1, max_length);
            }//改变最长长度和返回值
        }
        return res;
        
    }
};

解题思路2：

第二种思路是使用动态规划的方法。我们用P[i, j]表示字符串中i到j位置的子串；如果这个串是回文字符串则我们设定为1；如果这个子串不是回文字符串我们则设定为0。这样我们构建一个二维的数组用来保存是否是回文的信息；然后根据一下三种情况来进行修改数组中的信息。

  • 如果i = j的情况，则P[i,j]设定为1；
  • 如果j = i + 1情况，则判断s[i]和s[j]是否相等；相等为1否则为1；
  • 如果j > i + 1的情况，我们先判断s[i]和s[j]的情况，不相等则设定为1；如果相等的情况下则P[i,j] = P[i+1,j-1]

需要注意的地方是，我们则判断P[i, j]的时候用的是P[i + 1, j - 1]的情况，所以我们需要先知道P[i + 1,j - 1]的情况，这样决定了我们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
class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() == 0) return s;
        int max_length = 1;//记录当前的最长长度
        string res = s.substr(0, 1);//设定第一个为结果
        int dp[s.size()][s.size()] = {0};//设定全部动态数组为0
        
        for (int i = s.size() - 1; i >= 0; i--){
        //i从末尾开始遍历起
            for (int j = i; j < s.size(); j++){
            //j从i开始遍历到字符串末尾
                if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])){
     //这里面先判断了当前两个位置的字符是否相等的情况，只有相等后才有后序判断
     //如果相等；间隔小于等于1的情况直接设定为1；不然根据P[i + 1, j - 1]的情况
                    dp[i][j] = 1;
                    if (j - i + 1 > max_length){
                        max_length = j - i + 1;
                        res = s.substr(i, j - i + 1);
                    }
                }
            }
        }
       return res; 
    }
};