Voyz's Studio.

LeetCode算法笔记--回文子串

字数统计: 279阅读时长: 1 min
2021/03/17 Share

LeetCode算法笔记-Day73

647. 回文子串

给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。

1
2
3
4
5
6
7
8
9
· 示例1
输入:"abc"
输出:3
解释:三个回文子串: "a", "b", "c"

· 示例2
输入:"aaa"
输出:6
解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

动态规划

2324.png

Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* @param {string} s
* @return {number}
*/
var countSubstrings = function(s) {
let len = s.length,
s_arr = s.split('');
let dp = new Array(len).fill(new Array(len)),
count = 0;

for(let j=0;j<len;j++){

for(let i=0;i<j+1;i++){
if(i == j || (j-i == 1 && s_arr[i] == s_arr[j])){
dp[j][i] = true;
console.log(i,j)
count += 1;
}else if(j-i == 1 && s_arr[i] != s_arr[j]){
dp[j][i] = false;
}else {
if(s_arr[i] == s_arr[j]){
dp[j][i] = dp[j-1][i+1];
if(!!dp[j][i]) {
count += 1;
}
}else{
dp[j][i] = false;
}
}
}
}

return count;
};
CATALOG
  1. 1. LeetCode算法笔记-Day73
    1. 1.1. 647. 回文子串
    2. 1.2. 动态规划
      1. 1.2.1. Answer: