回文串-leetcode

[alittlepeara]

647. 回文子串

题目

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。 

示例 1：输入：s = "abc" 输出：3 解释：三个回文子串: "a", "b", "c"

示例 2：输入：s = "aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

思路：

我只能想到暴力解法……时间复杂度是三次方

动态规划：dp[i][j] 是boolean型，时间复杂度是二次方，空间复杂度也是二次方

扩展中心点法： abc有5个中心点（算上每个字母中间的空格） n个字母有2n-1个中心点， 01234 0 1 2 时间复杂度是二次方，空间复杂度是常数

代码（扩展中心点）

package 回文子串;
public class better_Solution {
    public int countSubstrings(String s) {
        int n = 2*s.length()-1;
        int re = 0;
        for(int count = 0;count<n;count++){
            int i = count/2;
            int j = i+count%2;
            while(i>=0&&j<s.length()&&s.charAt(i) == s.charAt(j)) {
                    i--;
                    j++;
                    re++;
            }
        }
        return re;
    }
}

⚠这里我本来写的是

while(i>=0&&j<s.length()) {
                if (s.charAt(i) == s.charAt(j)) {
                    i--;
                    j++;
                    re++;
                }
        
            }

一直说我超出时间限制，看上去和正确的一样，其实不一样，正确的如果不满足第i 位=第 j 位就推出循环了，但是这种写法还会进入下一轮循环 所以应该加个else break

132. 分割回文串 II

题目：

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。 返回符合要求的 最少分割次数 。 

示例 1：输入：s = "aab" 输出：1 解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。 示例 2：输入：s = "a" 输出：0 示例 3：输入：s = "ab" 输出：1

思路：

一开始没有思路TT。后面看了代码随想录，先去做了上面那道题，然后自己写出来了动态规划法，先用一个boolean的二维dp记录哪些是回文子串，然后用一个一维int的dp1记录前i位最少分割次数； 但是也修修改改好久，一个是因为搞错了i++和i+1； 还有一个是boolean的dp循环写错了，一开始写成了最普通的那种两层循环，其实因为dp[i][j]循环里面要用到dp[i+1][j-1]，所以应该写成这样：

 for(int i = 0;i<n;i++){
            for(int j = i;j>=0;j--){

好像之前也写过类似的，是写成12，23，34，13，24，14这样的循环

代码：

public class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][]dp = new boolean[n][n];
        for(int i = 0;i<n;i++){
            for(int j = i;j>=0;j--){
                if(s.charAt(i) == s.charAt(j)){
                    if(i<=j+1){
                        dp[j][i] = true;
                    }
                    else if(dp[j+1][i-1]){
                        dp[j][i] = true;
                    }
                }
            }
        }
        int[]dp1 = new int[n+1];
        dp1[0] = -1;
        for(int i = 2;i<=n;i++){
            dp1[i] = dp1[i-1]+1;
            for(int j = i-1;j>0;j--){
                if(dp[j-1][i-1]){
                        dp1[i] = Math.min(dp1[i], dp1[j - 1] + 1);
                }
            }
        }
        return dp1[n];
    }
}