0%

leetcode每日一题-回文子串

Posted on In ,

回文子串

image1

暴力法

枚举出所有子串，然后再判断这些子串是否回文。

1
class Solution {
2
    public int countSubstrings(String s) {
3
        int n = s.length();
4
        int ans = 0;
5
        for(int i=0; i<n; i++){
6
            for(int j=i; j<n; j++){
7
                if(isPalindromic(s.substring(i,j+1))){
8
                    ans++;
9
                }
10
            }
11
        }
12
        return ans;
13
    }
14
    public boolean isPalindromic(String s){
15
        int left = 0;
16
        int right = s.length()-1;
17
        while(left < right){
18
            if(s.charAt(left) != s.charAt(right)){
19
                return false;
20
            }
21
            left++;
22
            right--;
23
        }
24
        return true;
25
    }
26
}

复杂度分析：

  • 时间复杂度：$O(n^3)$。
  • 空间复杂度：$O(1)$。

中心扩展法

枚举回文串的扩展中心，并进行扩展，在扩展的过程中计算回文子串。扩展中心可能是一个字符，也可能是两个字符，需要分类讨论。

1
class Solution {
2
    public int countSubstrings(String s) {
3
        int n = s.length();
4
        int ans = 0;
5
        for(int i=0; i<n; i++){
6
            int left = i, right = i;
7
            while(left>=0 && right<n && s.charAt(left)==s.charAt(right)){
8
                left--;
9
                right++;
10
                ans++;
11
            }
12
        }
13
        for(int i=0; i<n-1; i++){
14
            int left=i, right=i+1;
15
            if(s.charAt(left) != s.charAt(right)){
16
                continue;
17
            }
18
            while(left>=0 && right<n && s.charAt(left)==s.charAt(right)){
19
                left--;
20
                right++;
21
                ans++;
22
            }
23
        }
24
        return ans;
25
    }
26
}

复杂度分析：

  • 时间复杂度：$O(n^2)$。
  • 空间复杂度：$O(1)$。