8000 fix leetcode 0005 with go · dryyun/algorithms-note@991cb1c · GitHub
[go: up one dir, main page]
Skip to content

Commit 991cb1c

Browse files
dryyundryyun
committed
fix leetcode 0005 with go
1 parent 9df966a commit 991cb1c

File tree

7 files changed

+142
-34
lines changed

7 files changed

+142
-34
lines changed

‎LeetCode/Go-Solutions/ProblemSet/0005.Longest_Palindromic_Substring/README.md

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
# 5. 最长回文子串
2+
3+
## 链接
4+
https://leetcode-cn.com/problems/longest-palindromic-substring/
5+
6+
## 难度
7+
中等
8+
9+
## 描述
10+
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
11+
12+
示例 1：
13+
```text
14+
输入: "babad"
15+
输出: "bab"
16+
注意: "aba" 也是一个有效答案。
17+
```
18+
19+
示例 2：
20+
```text
21+
输入: "cbbd"
22+
输出: "bb"
23+
```
24+
## 思路
25+
https://www.jianshu.com/p/a7741619dd58
26+
动态规划
27+
dp[i][j]，表示子串 i->j 是否是回文，基于判断 s[i]==[sj] && dp[i+1][j-1]
28+
存在情况
29+
- aa，i = 0，j = 1，dp[i+1][j-1] = dp[1][0] ，其实肯定符合条件
30+
- aba，i = 0，j = 2， dp[i+1][j-1] = dp[1][1]，其实也肯定符合条件
31+
32+
所以推出判断 s[i] == s[j] && (j-i < 3 || dp[i+1][j-1])
33+

‎LeetCode/Go-Solutions/ProblemSet/0005.Longest_Palindromic_Substring/longest-palindromic-substring.go

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
//package _005_Longest_Palindromic_Substring
2+
3+
package main
4+
5+
import "fmt"
6+
7+
func main() {
8+
//fmt.Println(longestPalindrome("s"))
9+
fmt.Println(longestPalindrome("babad"))
10+
fmt.Println(longestPalindrome("cbbd"))
11+
fmt.Println(longestPalindrome("abc"))
12+
fmt.Println(longestPalindrome("aaaa"))
13+
}
14+
15+
func longestPalindrome(s string) string {
16+
length := len(s)
17+
if length <= 1 {
18+
return s
19+
}
20+
21+
// 基于题目描述，字符串长度不超过 1000，声明二维数组
22+
dp := [1000][1000]bool{}
23+
24+
// 声明二维 slice
25+
//dp := make([][]bool, length)
26+
//for i := range dp {
27+
// dp[i] = make([]bool, length)
28+
//}
29+
30+
var st, sl int // string start，start len
31+
for i := length - 2; i >= 0; i-- {
32+
dp[i][i] = true
33+
for j := i + 1; j < length; j++ {
34+
if s[i] == s[j] && (j-i < 3 || dp[i+1][j-1]) {
35+
dp[i][j] = true
36+
if j-i > sl {
37+
st = i
38+
sl = j - i
39+
}
40+
}
41+
}
42+
}
43+
return s[st : st+sl+1]
44+
}

‎LeetCode/ProblemSet/005.Longest Palindromic Substring/longest-palindromic-substring.js

Lines changed: 14 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -8,31 +8,25 @@ var longestPalindrome = function (s) {
88
return s;
99
}
1010

11-
let start = 0, sl = 1;
12-
13-
let dp = [];
14-
dp[0] = [];
15-
dp[0][0] = true;
16-
for (let i = 1; i < len; i++) {
17-
dp[i] = [];
18-
dp[i][i] = true;
19-
if (s[i 1E0A - 1] === s[i]) {
20-
start = i - 1;
21-
sl = 2;
22-
dp[i - 1][i] = true;
23-
}
11+
let dp = []
12+
for (let i = 0; i < len; i++) {
13+
dp[i] = new Array(len);
2414
}
2515

26-
for (let k = 3; k <= len; k++) {
27-
for (let i = 0; i <= len - k; i++) {
28-
if (s[i] === s[i + k - 1] && dp[i + 1][i + k - 2]) {
29-
dp[i][i + k - 1] = true;
30-
start = i;
31-
sl = k;
16+
let st = 0, sl = 0
17+
for (let i = len - 2; i >= 0; i--) {
18+
dp[i][i] = true
19+
for (let j = i + 1; j < len; j++) {
20+
if (s[i] === s[j] && (j - i < 3 || dp[i + 1][j - 1])) {
21+
dp[i][j] = true
22+
if (j - i > sl) {
23+
st = i
24+
sl = j - i
25+
}
3226
}
3327
}
3428
}
35-
return s.substr(start, sl);
29+
return s.substring(st, st + sl + 1)
3630
};
3731

3832
console.log(longestPalindrome('babad'));

‎notes/gather.js

Lines changed: 0 additions & 14 deletions
This file was deleted.

‎notes/palindrome/README.md

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
# 回文 palindrome
2+
3+
## 判断字符串是否是回文
4+
查看 code.IsPalindrome 实现
5+
6+
## 求字符串最长回文子串
7+
leetcode - 0005

‎notes/palindrome/code.go

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package palindrome
2+
3+
// 判断回文，外部可见函数
4+
func IsPalindrome(s string) bool {
5+
return isPalindromeByIndex(s, 0, len(s)-1)
6+
}
7+
8+
// 判断回文，外部不可见
9+
func isPalindromeByIndex(s string, start int, end int) bool {
10+
for start < end && s[start] == s[end] {
11+
start++
12+
end--
13+
}
14+
return start >= end
15+
}

‎notes/palindrome/code_test.go

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package palindrome
2+
3+
import (
4+
"github.com/stretchr/testify/assert"
5+
"testing"
6+
)
7+
8+
func TestOne(t *testing.T) {
9+
tests := []struct {
10+
s string
11+
r bool
12+
}{
13+
{
14+
s: "a",
15+
r: true,
16+
},
17+
{
18+
s: "ab",
19+
r: false,
20+
},
21+
{
22+
s: "aba",
23+
r: true,
24+
},
25+
}
26+
for _, v := range tests {
27+
assert.Equal(t, IsPalindrome(v.s), v.r, "should be equal")
28+
}
29+
}

0 commit comments

Comments
 (0)
0