forked from TheAlgorithms/Go
-
Notifications
You must be signed in to change notification settings - Fork 0
/
longestpalindromicsubsequence.go
56 lines (49 loc) · 1011 Bytes
/
longestpalindromicsubsequence.go
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// longest palindromic subsequence
// http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/
package dynamic_programming
// LpsRec function
func LpsRec(word string, i, j int) int {
if i == j {
return 1
}
if i > j {
return 0
}
if word[i] == word[j] {
return 2 + LpsRec(word, i+1, j-1)
}
return Max(LpsRec(word, i, j-1), LpsRec(word, i+1, j))
}
// LpsDp function
func LpsDp(word string) int {
N := len(word)
dp := make([][]int, N)
for i := 0; i < N; i++ {
dp[i] = make([]int, N)
dp[i][i] = 1
}
for l := 2; l <= N; l++ {
// for length l
for i := 0; i < N-l+1; i++ {
j := i + l - 1
if word[i] == word[j] {
if l == 2 {
dp[i][j] = 2
} else {
dp[i][j] = 2 + dp[i+1][j-1]
}
} else {
dp[i][j] = Max(dp[i+1][j], dp[i][j-1])
}
}
}
return dp[1][N-1]
}
/*
func main() {
// word := "aaabbbbababbabbabbabf"
word := "aaaabbbba"
fmt.Printf("%d\n", lpsRec(word, 0, len(word)-1))
fmt.Printf("%d\n", lpsDp(word))
}
*/