Voyz's Studio.

LeetCode算法笔记--回文子串

算法题 热题HOT100 动态规划
字数统计: 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：
Total : 137
2021
2020
2019
2018
技术贴 JavaScript Flutter 算法题 热题HOT100 哈希表 滑动窗口 回溯算法 链表 二分法 矩阵 动态规划 贪心算法 指针 快速排序 迭代 二叉树 数组 快慢指针 排序 背包问题 单调栈 栈 DFS 岛屿问题 React Native React 旅行记 效率工具 python 小程序 英语 生活 足球 算法 性能优化 ES6 TypeScript koa