[[434467]]

給定一個字符串，你的任務是計算這個字符串中有多少個回文子串。

具有不同開始位置或結束位置的子串，即使是由相同的字符組成，也會被視作不同的子串。

示例 1：

輸入："abc" 
 
輸出：3 
 
解釋：三個回文子串: "a", "b", "c" 

示例 2：

輸入："aaa" 
 
輸出：6 
 
解釋：6個回文子串: "a", "a", "a", "aa", "aa", "aaa" 

提示：

• 輸入的字符串長度不會超過 1000 。

解法一：暴力法

let countSubstrings = function(s) { 
  let count = 0 
  for (let i = 0; i < s.length; i++) { 
    for (let j = i; j < s.length; j++) { 
      if (isPalindrome(s.substring(i, j + 1))) { 
        count++ 
      } 
    } 
  } 
  return count 
} 
 
let isPalindrome = function(s) { 
  let i = 0, j = s.length - 1 
  while (i < j) { 
    if (s[i] != s[j]) return false 
    i++ 
    j-- 
  } 
  return true 
} 

復雜度分析：

• 時間復雜度：O(n3)
• 空間復雜度：O(1)

解法二：動態規劃

一個字符串是回文串，它的首尾字符相同，且剩余子串也是一個回文串。其中，剩余子串是否為回文串，就是規模小一點的子問題，它的結果影響大問題的結果。

我們怎么去描述子問題呢?

顯然，一個子串由兩端的 i 、j 指針確定，就是描述子問題的變量，子串 s[i...j] ( dp[i][j] ) 是否是回文串，就是子問題。

我們用二維數組記錄計算過的子問題的結果，從base case出發，像填表一樣遞推出每個子問題的解。

    j 
    a  a  b  a 
i a ✅ 
  a    ✅   
  b       ✅ 
  a          ✅ 

注意： i<=j ，只需用半張表，豎向掃描

所以：

i === j：dp[i][j]=true 
j - i == 1 && s[i] == s[j]：dp[i][j] = true 
j - i > 1 && s[i] == s[j] && dp[i + 1][j - 1]：dp[i][j] = true 

即：

s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1]): dp[i][j]=true 

否則為 false

代碼實現：

let countSubstrings = function(s) { 
  const len = s.length 
  let count = 0 
  const dp = new Array(len) 
 
  for (let i = 0; i < len; i++) { 
    dp[i] = new Array(len).fill(false) 
  } 
  for (let j = 0; j < len; j++) { 
    for (let i = 0; i <= j; i++) { 
      if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) { 
        dp[i][j] = true 
        count++ 
      } else { 
        dp[i][j] = false 
      } 
    } 
  } 
  return count 
} 

代碼實現(優化)：

把上圖的表格豎向一列看作一維數組，還是豎向掃描，此時僅僅需要將 dp 定義為一維數組即可

let countSubstrings = function(s) { 
  const len = s.length 
  let count = 0 
  const dp = new Array(len) 
 
  for (let j = 0; j < len; j++) { 
    for (let i = 0; i <= j; i++) { 
      if (s[i] === s[j] && (j - i <= 1 || dp[i + 1])) { 
        dp[i] = true 
        count++ 
      } else { 
        dp[i] = false 
      } 
    } 
  } 
  return count; 
} 

復雜度分析：

• 時間復雜度：O(n2)
• 空間復雜度：O(n)

leetcode：https://leetcode-cn.com/problems/palindromic-substrings/solution/leetcode647hui-wen-zi-chuan-by-user7746o/