leetcode_day49

今日内容：

• 647. 回文子串 medium
• 516. 最长回文子序列 medium

647. 回文子串

题目：

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

思路：

1. 确定dp含义
   dp[i][j]表示区间s[i:j]是不是回文串
   
2. 确定状态转移
   

• s[i] == s[j]
  • j - i <= 1，i和j相同或挨着，dp[i][j] = true;
  • else，dp[i][j] = dp[i+1][j-1]，看内部是不是回文串
• s[i] != s[j]：对不上，s[i:j]不可能是回文串了，false
  

3. 初始化
   全false

代码

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int ans = 0;
        for(int i = s.size() - 1;i >= 0;i--) {
            for(int j = i;j < s.size();j++) {
                if(s[i] == s[j]) {
                    if(i == j || i + 1 == j || dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
};

双指针写法

class Solution {
public:
    int countSubstrings(string s) {
        //复习双指针写法
        int ans = 0;
        for(int i = 0;i < s.size();i++) {
            ans += count(s, i, i);
            ans += count(s, i, i + 1);
        }
        return ans;
    }
    int count(string s, int mid1, int mid2) {
        if(mid2 >= s.size()) return 0;
        int res = 0;
        int left = mid1, right = mid2;
        while(left >= 0 && right < s.size()) {
            if(s[left] == s[right]) res++;
            else break;
            left--, right++;
        }
        return res;
    }
};

516. 最长回文子串

题目：

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：
- 输入：s = "bbbab" - 输出：4 - 解释：一个可能的最长回文子序列为 "bbbb" 。

提示：
- 1 <= s.length <= 1000 - s 仅由小写英文字母组成

思路：

1. 确定dp含义：
   dp[i][j]表示区间s[i:j]内的最长回文子串长度
   
2. 确定状态转移：
   

• s[i] == s[j]
  • i == j，dp[i][j]=1
  • dp[i][j] = dp[i-1][j-1]+2
• s[i] != s[j]: max(dp[i-1][j], dp[i][j-1])

3. 初始化
   相等的ij就置1

代码

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        for(int i = 0;i < s.size();i++) dp[i][i] = 1;
        for(int i = s.size() - 2;i >= 0;i--) {
            for(int j = i + 1;j < s.size();j++) {
                if(s[i] == s[j]) {
                    dp[i][j] = dp[i+1][j-1] + 2;
                }
                else {
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][s.size() - 1];
    }
};

其他

动态规划跟着carl刷完了，提亮看起来貌似也有这么多，但其中过半都不是自己独立做出来的，看一半题解再做、看了一半还是不会于是全抄……动态规划仍然有很多要学，仍然要多做题，今天的两道题都没有做出来，找其他的回文题仍然不会。

在做dp专题时其实有很多题的难点是想到要用dp，而做专题本身就已经告诉你每道题都可以用dp，而且carl的题安排精妙，相邻的题很多都是相同的套路，如果单拿出来做，我大概率是做不出出来的，上周周赛的Q4很像完全背包专题中的一道题，但写出来不是TLE就是WA，看评论才发现不能直接dp，所以刷题之路任重道远，戒骄戒躁，不能太依赖题解，要多自己独立思考，更不能潜移默化地被评论、tag提示。不能3分钟没思路就跑去看题解了。