LeetCode Ts-647. Palindromic Substrings

    AllenLi
    Result

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

    Related Posts