【算法题】LeeCode 回文子字符串的个数

共计 905 个字符，预计需要花费 3 分钟才能阅读完成。

题目

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

提示:

1 <= s.length <= 1000
s 由小写英文字母组成

示例1

输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”

示例2

输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

JAVA解法

import java.util.Scanner;

/**
 * @since 2022年4月26日
 */
public class LeeCode_020 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();

        System.out.println(countSubstrings(line));

    }

    public static int countSubstrings(String line) {
        char[] chars = line.toCharArray();
//        StringBuilder builder = new StringBuilder();
        int count = 0;
        for (int i = 0; i < chars.length; i++) {
            for (int j = 0; j < chars.length; j++) {
                if (j < i || chars[i] != chars[j]) {
                    continue;
                }
                int l = i; // 定义最左边指针
                int r = j; // 定义最右边指针
                // 思路：两边向中间移动指针，判断回文字符
                while (l <= r) {
                    // 一旦出现不对称就跳出，说明不符合回文规则
                    if (chars[l] != chars[r]) {
                        r = -2;
                        break;
                    }
                    l++;
                    r--;
                }

                // -2就是个标记,预示本区间字符串不符合回文规则
                if (r != -2) {
                    count++;
//                    builder.append(line, i, temp + 1).append(", ");
                }
            }
        }
//        System.out.println(builder);
        return count;
    }
}