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

  • A+
所属分类:编程茶楼


共计 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”

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;
    }
}
  • 我的微信
  • 这是我的微信扫一扫
  • weinxin
  • 我的微信公众号
  • 我的微信公众号扫一扫
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: