当前位置:网站首页>力扣刷题647.回文子串
力扣刷题647.回文子串
2022-06-13 04:19:00 【grt要一直一直努力呀】
方法一:动态规划法
dp[ i ][ j ]表示字符串s在【i,j】区间内,是一个回文子串。
class Solution {
public int countSubstrings(String s) {
boolean[][] dp = new boolean[s.length()][s.length()];
int ans = 0;
for(int j = 0; j<s.length(); j++){
for(int i = 0; i<=j; i++){
if(s.charAt(i) == s.charAt(j) && (j-i<2 || dp[i+1][j-1])){
dp[i][j] = true;
ans++;
}
}
}
return ans;
}
}
时间复杂度为o(n^2),空间复杂度为o(n ^ 2),注意第7行的括号,要不然出错。
边栏推荐
- 史上最详细的Swin-Transformer 掩码机制(mask of window attentation)————shaoshuai
- [test development] advanced part - Classification of various test technologies
- The data obtained from mongodb query data command is null
- Lenovo notebook computer uses the insert key. When the mouse becomes a small square, how to solve it
- EMC整改纲要
- Uni app dynamic add style dynamic bind background image invalid
- 5g China Unicom ap:b SMS ASCII transcoding requirements
- Idea Download
- Cache read / write -- write
- Solution to failure to download files by wechat scanning QR code
猜你喜欢
Ladder race
Unity Shader 学习 004-Shader 调试 平台差异性 第三方调试工具
Interpretation of mobile phone private charging protocol
Et framework -22 creating serverinfo entities and events
MCU: NEC protocol infrared remote controller
环评图件制作-数据处理+图件制作
[test development] basic concepts related to testing
leetcode. 1 --- sum of two numbers
MCU: RS485 communication and Modbus Protocol
R: Airline customer value analysis practice
随机推荐
[kubernetes series] pod chapter actual operation
Zoom and move the H5 part of the mobile end
SCM: introduction and operation of EEPROM
Real time requirements for 5g China Unicom repeater network management protocol
The most detailed swing transformer mask of window attachment in history -- Shaoshuai
dumi 搭建文檔型博客
Solution to failure to download files by wechat scanning QR code
PAT 1054 The Dominant Color
干预分析 + 伪回归
MySQL索引
[test development] use case
【LeetCode】860. Change with lemonade (2 brushes for wrong questions)
Promise combined with await
[automated test] what you need to know about unittest
[笔记]vs2015 编写汇编masm32之使用MASM32库
Interpretation and implementation of proxy mode
2019 Blue Bridge Cup
Ladder race
Lambda end operation count
【自动化测试】关于unittest你需要知道的事