当前位置:网站首页>力扣刷题647.回文子串

力扣刷题647.回文子串

2022-06-13 04:19:00 grt要一直一直努力呀

在这里插入图片描述
方法一:动态规划法

dp[ i ][ j ]表示字符串s在【i,j】区间内,是一个回文子串。

在这里插入图片描述

class Solution {
    
    public int countSubstrings(String s) {
    
       boolean[][] dp = new boolean[s.length()][s.length()];
       int ans = 0;
       for(int j = 0; j<s.length(); j++){
    
           for(int i = 0; i<=j; i++){
    
               if(s.charAt(i) == s.charAt(j) && (j-i<2 || dp[i+1][j-1])){
    
                   dp[i][j] = true;
                   ans++;
               }
           }
       }
       return ans;
    }
}

时间复杂度为o(n^2),空间复杂度为o(n ^ 2),注意第7行的括号,要不然出错。

原网站

版权声明
本文为[grt要一直一直努力呀]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_44870115/article/details/125220151