Online Judge►LeetCode

[LeetCode] 647 - Palindromic Substrings

題意

輸出字串中回文子字串的個數。

解法

DP。

1
2
3
dp(i, j) 代表從 i 開始至 j 的子字串是否為回文
dp(i, j) = true if s(i) = s(j) & dp(i+1, j-1) = true
	 = false else

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
  let count = 0;
  let bool = Array.apply(null, Array(s.length+1)).map(row => new Array(s.length+1).fill(true));
  for ( var i = s.length - 1 ; i >= 0 ; i -- ){
    for ( var j = i + 1 ; j < s.length ; j ++ ){
      if ( s[i] === s[j] && bool[i+1][j-1] === true ){
        bool[i+1][j-1] = true;
        count ++;
      } else {
        bool[i][j] = false;
      }
    }
  }
  return count + s.length;
};