最长回文子串-三种DP实现

系统管理员 2023-05-31 02:54 6阅读 0赞

# 最长回文子串 #

> https://leetcode-cn.com/problems/longest-palindromic-substring/

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
    输出: "bb"

用动态规划来做，列举了三种解法

### 文章目录 ###

*  最长回文子串
 *   *  解法一
     *  解法二
     *  解法三

## 解法一 ##

*  动态规划求解：
    
     *  `map[i][j]`中，i表示起点坐标，j表示长度
     *  `map[i][1] = 1`，单个的字符同样为回文串
     *  当`s[i] == s[i+1]`时候， `map[i][2] = 2`，连续的串同样为回文串
     *  `map[i-1][j+2] = j+2` 当且仅当，`map[i][j]`非零（即对应的字符串为回文串），且`s[i-1] == s[i+j]`（即，两边同时扩充一个位置），所以长度就是其本身
 *  T: 156 ms M: 14.8 MB

class Solution { 
    public:
        string longestPalindrome(string s) { 
            if (s.size() < 2)
                return s;
            int map[2000][2001];
            int total = 1, start=0;
            for (int i = 0; i < s.size(); ++i) map[i][1] = 1;
            for (int i = 0; i < s.size()-1; ++i){ 
                if (s[i] == s[i+1]) { 
                    map[i][2] = 2;
                    total = 2;
                    start = i;
                }else { map[i][2] = 0;}
            }
            for (int j = 3; j <= s.size(); ++j){ 
                for (int i = 0;i <= s.size() - j; ++i){ 
                    if (map[i+1][j-2] != 0 && s[i] == s[i+j-1]) { 
                        map[i][j] = j;
                        if (total < map[i][j]){ 
                            total = map[i][j];
                            start = i;
                        }
                    } else map[i][j] = 0;
                }
            }
            return s.substr(start, total);
        }
    };

## 解法二 ##

*  T: 124 ms M: 8.8 MB

**在解法一的基础上做了改进，目的是降低空间需求。**

其实很明显，奇数长度的回文串和偶数长度的回文串之间是没有直接关联的。也就是，已知回文串，两边同时扩张一个位置才可能有依据判断是否为回文串。这样的性质将回文串明显的分为奇偶两种可能。

*  用取余的方式判断奇偶，就将原来的`1000 * 1001`的空间要求缩短到了 `1000 * 2`

class Solution { 
    public:
        string longestPalindrome(string s) { 
            if (s.size() < 2)
                return s;
            int map[1000][2];
            int total = 1, start=0;
            for (int i = 0; i < s.size(); ++i) map[i][1] = 1;
            for (int i = 0; i < s.size()-1; ++i){ 
                if (s[i] == s[i+1]) { 
                    map[i][2 % 2] = 2;
                    total = 2;
                    start = i;
                }else { map[i][2 % 2] = 0;}
            }
            for (int j = 3; j <= s.size(); ++j){ 
                for (int i = 0;i <= s.size() - j; ++i){ 
                    if (map[i+1][(j-2) % 2] != 0 && s[i] == s[i+j-1]) { 
                        map[i][j%2] = j;
                        if (total < map[i][j % 2]){ 
                            total = map[i][j % 2];
                            start = i;
                        }
                    } else map[i][j%2] = 0;
                }
            }
            return s.substr(start, total);
        }
    };

## 解法三 ##

*  T: 80 ms M: 9 MB

将解法二再改进为只需要一维的数组。  
明显，我们可以先做偶数长度的计算，之后，再算奇数的时候，只需要把原来的非0部分或者是更大的部分覆盖掉就好了。

此外，这里还使用动态分配内存的方式。由于每次调用该函数时都不需要分配这么多的内存，需要的时间就会更短。  
但同时对于动态分配内存，对于内存的存储和释放会需要更多的空间，因此空间上反而没有更缓和。

class Solution { 
    public:
        string longestPalindrome(string s) { 
            if (s.size() < 2)
                return s;
            int *map;
            map = new int[s.size()+1];
            int total = 1, start=0;
            
            for (int i = 0; i < s.size()-1; ++i){ 
                if (s[i] == s[i+1]) { 
                    map[i] = 2;
                    total = 2;
                    start = i;
                }else { map[i] = 0;}
            }
            
            for (int j = 4; j <= s.size(); j+=2){ 
                for (int i = 0;i <= s.size() - j; ++i){ 
                    if (map[i+1] != 0 && s[i] == s[i+j-1]) { 
                        map[i] = j;
                        if (total < map[i]){ 
                            total = map[i];
                            start = i;
                        }
                    } else map[i] = 0;
                }
            }
            
            
            for (int i = 0; i < s.size(); ++i) if (!map[i]) map[i] = 1;
            
            for (int j = 3; j <= s.size(); j+=2){ 
                for (int i = 0;i <= s.size() - j; ++i){ 
                    if (map[i+1] != 0 && s[i] == s[i+j-1]) { 
                        map[i] = j;
                        if (total < map[i]){ 
                            total = map[i];
                            start = i;
                        }
                    } else map[i] = 0;
                }
            }
            
            delete[]map;
            return s.substr(start, total);
        }
    };