LeetCode 647. 回文子串
题目描述
思路分析
中心扩散法
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func countSubstrings(s string) int {
n := len(s)
res := 0
// 中心扩展法
for i := 0; i < n; i++ {
res += expandAroundCenter(s, i, i)
res += expandAroundCenter(s, i, i+1)
}
return res
}
func expandAroundCenter(s string, left, right int) int {
count := 0
n := len(s)
for left >= 0 && right < n && s[left] == s[right] {
count++
left--
right++
}
return count
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func countSubstrings(s string) int {
n := len(s)
res := 0
// 中心扩展法
var expand func(left, right int)
expand = func(left, right int) {
for left >= 0 && right < n && s[left] == s[right] {
res++
left--
right++
}
}
for i := 0; i < n; i++ {
expand(i, i)
expand(i, i+1)
}
return res
}
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
定义
dp[i][j]为s[i...j]是否是回文串
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
func countSubstrings(s string) int {
n := len(s)
dp := make([][]bool, n)
for i := range dp {
dp[i] = make([]bool, n)
}
res := 0
// 动态规划法
for length := 1; length <= n; length++ {
for start := 0; start <= n-length; start++ {
end := start + length - 1
if length == 1 {
dp[start][end] = true
} else if length == 2 {
if s[start] == s[end] {
dp[start][end] = true
}
} else {
if s[start] == s[end] && dp[start+1][end-1] {
dp[start][end] = true
}
}
if dp[start][end] {
res++
}
}
}
return res
}
- 时间复杂度：O(n^2)
- 空间复杂度：O(n^2)
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！