leetcode-647-Palindromic-Substrings

发表于   |  

TOREVIEW

描述

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

1
2
3
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

1
2
3
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

  1. The input string length won’t exceed 1000.

分析

遍历所有的字符，从中间往两边开始遍历。

解决方案1（Python）

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def countSubstrings(self, s: str) -> int:
        sLen, result = len(s), 0
        
        for i in range(2*sLen-1):
            left, right = i//2, i//2 + i%2
            while left >=0 and right < sLen and s[left] == s[right]:
                result += 1
                left -= 1
                right += 1
        return result

解决方案1(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int countSubstrings(string s) {
        if (s.empty()) {
            return 0;
        }
        int n = s.size(), result = 0;
        for (int i = 0; i < n; i++) {
            getMoreResult(s, i, i, result);
            getMoreResult(s, i, i+1, result);
        }
        return result;
    }
    
    void getMoreResult(string s, int i, int j, int& result) {
        while (i >= 0 && j < s.size() && s[i] == s[j]) {
            i--;
            j++;
            result++;
        }
    }
};

相关问题

题目来源