当前位置:   article > 正文

力扣做题记录——647.回文子串&5.最长回文子串_实验一:力扣 647 50

实验一:力扣 647 50

由于这两题的解法相似,因此本文将直接介绍通用解法,并直接给出两道题的代码。
方法1 动态规划法
首先本题可以使用动态规划法:

  • 状态:dq[i][j]表示字符串在[i, j]区间内的子串是否是一个回文串;
  • 状态转移方程:当s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])时,dp[i][j] = true,否则为false

解释:

  1. 当只有一个字符时,比如a自然是一个字符串;
  2. 当有两个字符时,如果两个字符相等,比如aa,也是一个回文串;
  3. 当有三个及以上字符时,比如ababa这个字符串,只要保证其两端字符相等,并且其内部也是回文串,那么整个字符串也是回文串。

代码

// 647.回文子串
int countSubstrings(string s) {
    vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
    int res = 0;
    for (int j = 0; j < s.size(); j++) {
        for (int i = 0; i <= j; i++) {
            if (s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                res++;
            }
        }
    }
    return res;
}

// 5.最长回文子串
string longestPalindrome(string s) {
    vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
    int max = 0;
    int left = 0;
    int right = 0;
    for (int j = 0; j < s.size(); j++) {
        for (int i = 0; i <= j; i++) {
            if (s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
            }
            if (dp[i][j] && j - i + 1 > max){
                max = j - i + 1;
                left = i;
                right = j;
            }
        }
    }
    return s.substr(left, right - left + 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

方法2 中心扩展法
这是一个比较巧妙的方法,实质的思路和动态规划的思路类似。
比如对一个字符串ababa,选择最中间的a作为中心点,往两边扩散,第一次扩散发现left指向的是bright指向的也是b,所以是回文串,继续扩散,同理ababa也是回文串。
这个是确定了一个中心点后的寻找的路径,然后我们只要寻找到所有的中心点,问题就解决了。
中心点一共有多少个呢?看起来像是和字符串长度相等,但你会发现,如果是这样,上面的例子永远也搜不到abab,想象一下单个字符的哪个中心点扩展可以得到这个子串?似乎不可能。所以中心点不能只有单个字符构成,还要包括两个字符,比如上面这个子串abab,就可以有中心点ba扩展一次得到,所以最终的中心点由2 * len - 1个,分别是len个单字符和len - 1个双字符。
如果上面看不太懂的话,还可以看看下面几个问题:

  • 为什么有 2 * len - 1 个中心点?
    aba 有5个中心点,分别是 a、b、c、ab、ba
    abba 有7个中心点,分别是 a、b、b、a、ab、bb、ba
  • 什么是中心点?
    中心点即 left 指针和 right 指针初始化指向的地方,可能是一个也可能是两个
  • 为什么不可能是三个或者更多?
    因为 3 个可以由 1 个扩展一次得到,4 个可以由两个扩展一次得到
    代码
// 647.回文子串
int countSubstrings(String s) {
    // 中心扩展法
    int ans = 0;
    for (int center = 0; center < 2 * s.size() - 1; center++) {
        // left和right指针和中心点的关系是?
        // 首先是left,有一个很明显的2倍关系的存在,其次是right,可能和left指向同一个(偶数时),也可能往后移动一个(奇数)
        // 大致的关系出来了,可以选择带两个特殊例子进去看看是否满足。
        int left = center / 2;
        int right = left + center % 2;

        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            ans++;
            left--;
            right++;
        }
    }
    return ans;
}

// 5.最长回文子串
pair<int, int> expandAroundCenter(const string& s, int left, int right) {
    while (left >= 0 && right < s.size() && s[left] == s[right]) {
        --left;
        ++right;
    }
    return {left + 1, right - 1};
}

string longestPalindrome(string s) {
    int start = 0, end = 0;
    for (int i = 0; i < s.size(); ++i) {
        auto [left1, right1] = expandAroundCenter(s, i, i);
        auto [left2, right2] = expandAroundCenter(s, i, i + 1);
        if (right1 - left1 > end - start) {
            start = left1;
            end = right1;
        }
        if (right2 - left2 > end - start) {
            start = left2;
            end = right2;
        }
    }
    return s.substr(start, end - start + 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
  • 45
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小蓝xlanll/article/detail/470788
推荐阅读
相关标签
  

闽ICP备14008679号