647. Palindromic Substrings

Leetcode 问题: 647. Palindromic Substrings
Categories:
Tags:

题目

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

传入一个 字串 s，计算所有这个字串的所有 palindromic 子字串 数量

Example

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

演算法

1. 检查起点为奇数及偶数个数的 Palindromic 子字串

如果起点是 Palindromic 字串，那选择一起点后，左右指标往左右移动后的字母也相同，那也一定是 Palindromic 字串

当左右指标检查的字母不同，则就不是 Palindromic 字串

奇数 Palindromic 字串

e.g. aba

字母 a b a
左指标 ↑
右指标 ↑

左右指标左右移动，检查字母相同，所以也是 Palindromic 字串

字母 a b a
左指标 ↑
右指标 ↑

偶数 Palindromic 字串

e.g. abba

字母 a b b a
左指标 ↑
右指标 ↑

左右指标左右移动，检查字母相同，所以也是 Palindromic 字串

字母 a b b a
左指标 ↑
右指标 ↑

答案

JavaScript

function countSubstrings(checkText) {
    // Palindromic 子字串数量
    var totalPalindromicSubstringCount = 0;
    // 设定检查指标
    var leftPointer = 0;
    var rightPointer = 0;
    // 检查 Palindromic 子字串数量
    for (var i = 0; i < checkText.length; i++) {
        // 检查「奇数」长度的 Palindromic 子字串
        // 左右起点相同
        leftPointer = i;
        rightPointer = i;
        while (leftPointer >= 0 && rightPointer < checkText.length && checkText[leftPointer] == checkText[rightPointer]) {
            // 当左右指标都在字串长度中，没有超出字串范围，比较左右字相同的话，则找到 Palindromic 子字串
            // Palindromic 子字串数量 + 1
            totalPalindromicSubstringCount++;
            // 移动左右指标，继续检查下两个字母
            leftPointer--;
            rightPointer++;
        }
        // 检查「偶数」长度的 Palindromic 子字串
        // 左右起点差一格
        leftPointer = i;
        rightPointer = i + 1;
        while (leftPointer >= 0 && rightPointer < checkText.length && checkText[leftPointer] == checkText[rightPointer]) {
            // 当左右指标都在字串长度中，没有超出字串范围，比较左右字相同的话，则找到 Palindromic 子字串
            // Palindromic 子字串数量 + 1
            totalPalindromicSubstringCount++;
            // 移动左右指标，继续检查下两个字母
            leftPointer--;
            rightPointer++;
        }
    }
    return totalPalindromicSubstringCount;
}

TypeScript

function countSubstrings(checkText: string): number {
    // Palindromic 子字串数量
    let totalPalindromicSubstringCount = 0;

    // 设定检查指标
    let leftPointer = 0;
    let rightPointer = 0;

    // 检查 Palindromic 子字串数量
    for (let i = 0; i < checkText.length; i++) {
        // 检查「奇数」长度的 Palindromic 子字串
        // 左右起点相同
        leftPointer = i;
        rightPointer = i;
        while (leftPointer >= 0 && rightPointer < checkText.length && checkText[leftPointer] == checkText[rightPointer]) {
            // 当左右指标都在字串长度中，没有超出字串范围，比较左右字相同的话，则找到 Palindromic 子字串
            // Palindromic 子字串数量 + 1
            totalPalindromicSubstringCount++;
            // 移动左右指标，继续检查下两个字母
            leftPointer--;
            rightPointer++;
        }

        // 检查「偶数」长度的 Palindromic 子字串
        // 左右起点差一格
        leftPointer = i;
        rightPointer = i + 1;
        while (leftPointer >= 0 && rightPointer < checkText.length && checkText[leftPointer] == checkText[rightPointer]) {
            // 当左右指标都在字串长度中，没有超出字串范围，比较左右字相同的话，则找到 Palindromic 子字串
            // Palindromic 子字串数量 + 1
            totalPalindromicSubstringCount++;
            // 移动左右指标，继续检查下两个字母
            leftPointer--;
            rightPointer++;
        }
    }

    return totalPalindromicSubstringCount;
};

参考资料