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;
};

參考資料