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,回傳符合回文字串的數量。 如果一個字串由前往後、由後往前的結果接相同,那就是一個回文。 子字串是字串內連續的字元序列。
Example 1:
Input: s = "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: s = "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
solution:
1. 定義 count 變數。
2. 建立中心擴展的函式,符合 palindromic 判斷條件的時候,count加一。
3. 遍歷 s 字串長度的迴圈,依對應次數呼叫中心擴展函式。
4. 回傳 count。
Code 1: BigO(n^2) Expand Around Center
function countSubstrings(s: string): number { let count: number = 0; const expandAroundCenter = (left: number, right: number): void => { while (left >= 0 && right < s.length && s[left] === s[right]) { count++; left--; right++; } }; for (let i = 0; i < s.length; i++) { expandAroundCenter(i, i); expandAroundCenter(i, i + 1); } return count; }