动态规划 Leetcode 647 回文子串

回文子串

Leetcode 647

学习记录自代码随想录

方法一：动态规划
要点：1.dp[i][j]定义为以区间s[i:j]是否为回文，是为true，否则为false；
2.递推公式（递推方法：从中间往两边递推）：if(s[i]==s[j])
if(j-i<=1)
result++;
dp[i][j] = true;
else if(dp[i+1][j-1])
result++;
dp[i][j] = true;
else
dp[i][j] = false;
3.遍历时注意方向和起始值for(int i = n-1; i >= 0; i–）
for(int j = i; j < n; j++)

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        // 1.dp[i][j] 为s[i:j]区间（左闭右闭）是否为回文子串
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        // 2.递推公式：if(s[i] == s[j]){
        //                if(j-i <= 1){
        //                    result++;dp[i][j] = true;
        //                }else if(dp[i+1][j-1]) result++;dp[i][j] = true; 
        //            }
        // 3.dp数组默认为false
        // 4.遍历顺序：正向遍历
        int result = 0;
        for(int i = n-1; i >= 0; i--){
            for(int j = i; j < n; j++){  // 注意遍历起始值
                if(s[i] == s[j]){
                    if(j - i <= 1){
                        result++;
                        dp[i][j] = true;    
                    }else if(dp[i+1][j-1]){
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
};

方法二：双指针法

// 双指针法 （递推方法：从中间往两边走）
class Solution{
public:
    int huiwen_number(const string& s, int i, int j, int n){
        int res = 0;
        while(i >= 0 && j < n && s[i] == s[j]){
            i--;
            j++;
            res++;
        }
        return res;
    }
    int countSubstrings(string s){
        int result = 0;
        for(int i = 0; i < s.size(); i++){
            result += huiwen_number(s, i, i, s.size());
            result += huiwen_number(s, i, i+1, s.size());
        }
        return result;
    }
};