中心扩展法求回文子串的长度

雨点打透心脏的1/2处 2024-03-22 20:36 65阅读 0赞

## 中心扩展法求回文子串的长度 ##

回文串是指正读和反读结果相同的字符串，如"level"、“deed”。本文介绍一种利用中心扩展法求解最长回文子串的方法。

### 算法思路 ###

给定一个字符串`s`，我们遍历字符串的每个字符，以当前字符为中心向两边扩展，同时记录扩展的回文子串的长度。由于回文串可以是奇数或偶数长度，我们分别考虑以当前字符为中心和以当前字符和下一个字符为中心的情况。

具体算法如下：

class Solution {
        
    public:
        string longestPalindrome(string s) {
        
            int n = s.length(); // 字符串长度
            if (n < 2) {
        
                return s; // 如果字符串长度小于2，直接返回原字符串
            }
            
            int start = 0; // 最长回文子串的起始位置
            int maxLength = 1; // 最长回文子串的长度
            
            for (int i = 0; i < n; i++) {
         // 遍历字符串
                // 对称中心是一个字符
                int len1 = expandAroundCenter(s, i, i); // 以当前字符为中心扩展，得到的回文子串长度
                // 对称中心是两个字符
                int len2 = expandAroundCenter(s, i, i + 1); // 以当前字符和下一个字符为中心扩展，得到的回文子串长度
                
                // 取最长的回文子串长度，并记录起始位置
                int curMaxLen = max(len1, len2);
                if (curMaxLen > maxLength) {
        
                    maxLength = curMaxLen;
                    start = i - (maxLength - 1) / 2;
                }
            }
            
            return s.substr(start, maxLength); // 返回最长回文子串
        }
        
    private:
        // 中心扩展法求回文子串的长度
        int expandAroundCenter(const string& s, int left, int right) {
        
            int n = s.length();
            while (left >= 0 && right < n && s[left] == s[right]) {
        
                left--;
                right++;
            }
            return right - left - 1;
        }
    };

### 代码解析 ###

首先，我们定义了一个名为`Solution`的类，其中包含了我们要实现的算法。该类中有一个公共成员函数`longestPalindrome`，用于接收一个字符串`s`并返回最长的回文子串。

在`longestPalindrome`函数中，我们首先获取输入字符串的长度。若长度小于2，则直接返回原字符串。否则，我们初始化回文子串的起始位置`start`为0，长度`maxLength`为1。

接下来，我们使用一个`for`循环遍历字符串`s`的每个字符，以当前字符作为中心向两边扩展。具体地，分别以当前字符为对称中心和以当前字符和下一个字符为对称中心进行扩展，计算得到的回文子串的长度。

然后，我们取两种扩展情况下的最大长度`curMaxLen`，并记录起始位置`start`。计算方法是将当前字符所在位置减去(`maxLength - 1`)的一半，即`i - (maxLength - 1) / 2`。

最后，我们返回使用`substr`函数从输入字符串`s`中提取最长回文子串，并以该结果作为函数的返回值。

另外，我们还实现了名为`expandAroundCenter`的私有成员函数，用于执行中心扩展法求解回文子串的长度。该函数使用了左右指针的方式，分别从对称中心向左右两边扩展，直到不满足回文串的条件为止。最终返回右指针和左指针的差值减1（因为循环结束后右指针与左指针已经错开了一个位置）。

### 总结 ###

通过使用中心扩展法，我们可以高效地求解给定字符串中的最长回文子串。该算法的时间复杂度为O(n^2)，其中n为字符串的长度。由于只使用了常数额外空间，因此空间复杂度为O(1)。