103 lines
2.0 KiB
Go
103 lines
2.0 KiB
Go
|
package main
|
|||
|
|
import (
|
|||
|
|
"fmt"
|
|||
|
|
"strings"
|
|||
|
|
)
|
|||
|
|
/*
|
|||
|
|
Given a string s, return the longest palindromic substring in s.
|
|||
|
|
|
|||
|
|
Example 1:
|
|||
|
|
|
|||
|
|
Input: s = "babad"
|
|||
|
|
Output: "bab"
|
|||
|
|
Note: "aba" is also a valid answer.
|
|||
|
|
Example 2:
|
|||
|
|
|
|||
|
|
Input: s = "cbbd"
|
|||
|
|
Output: "bb"
|
|||
|
|
Example 3:
|
|||
|
|
|
|||
|
|
Input: s = "a"
|
|||
|
|
Output: "a"
|
|||
|
|
Example 4:
|
|||
|
|
|
|||
|
|
Input: s = "ac"
|
|||
|
|
Output: "a"
|
|||
|
|
|
|||
|
|
|
|||
|
|
Constraints:
|
|||
|
|
|
|||
|
|
1 <= s.length <= 1000
|
|||
|
|
s consist of only digits and English letters.
|
|||
|
|
*/
|
|||
|
|
|
|||
|
|
/*
|
|||
|
|
Hints: If the string is 2 characters and they are both the same character then it is a palindrome (ie: aa or 11)
|
|||
|
|
|
|||
|
|
So you can use create a table to calculate a table where if table[i+1][j-1] is true and string[i+1] == string[j-1]
|
|||
|
|
then the substring string is a palindrome
|
|||
|
|
|
|||
|
|
You can see that i+1, j-1 is like two pointers with one going forward and the other going backwards
|
|||
|
|
|
|||
|
|
|
|||
|
|
a b a
|
|||
|
|
a 0 0 1
|
|||
|
|
b 0 1 0
|
|||
|
|
a 1 0 1
|
|||
|
|
*/
|
|||
|
|
func longestPalindrome(s string) string {
|
|||
|
|
/*
|
|||
|
|
If string s has a len = 1 then the longest palindrome is s
|
|||
|
|
|
|||
|
|
If string s has len = 2 and the two characters are the same then the longest palindrome is s
|
|||
|
|
*/
|
|||
|
|
|
|||
|
|
var n = len(s)
|
|||
|
|
|
|||
|
|
if n == 1 {
|
|||
|
|
return s
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
if n == 2 && s[0] == s[1] {
|
|||
|
|
return s
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// Generate memory table table[i][i] = true
|
|||
|
|
var output string
|
|||
|
|
dp := make([][]bool, n)
|
|||
|
|
for i:= 0; i < n - 1; i++ {
|
|||
|
|
dp[i] = make([]bool, n)
|
|||
|
|
dp[i][i] = true
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// Need to do this to access by index
|
|||
|
|
// see https://stackoverflow.com/questions/15018545/how-to-index-characters-in-a-golang-string
|
|||
|
|
strarr := strings.Split(s, "")
|
|||
|
|
// Also check for palidrome where length == 2 using s[i] == s[i+1]
|
|||
|
|
for i := 0; i < n - 1; i++ {
|
|||
|
|
if (strarr[i] == strarr[i+1]) {
|
|||
|
|
dp[i][i+1] = true
|
|||
|
|
output = s[i:i+1]
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// n = 5
|
|||
|
|
// i = 2; x = 0; y = 1
|
|||
|
|
|
|||
|
|
// Find substring where n > 2
|
|||
|
|
for i := 2; i < n - 1; i++ {
|
|||
|
|
for x := 0; x < n - i; x++ {
|
|||
|
|
// starting at x find the end idx (len substring - 1 )
|
|||
|
|
y := x + i - 1
|
|||
|
|
if (dp[x+1][y-1] && strarr[x] == strarr[y]) {
|
|||
|
|
output = s[x:(y+1)]
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
return output
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
func main () {
|
|||
|
|
fmt.Println(longestPalindrome("babad"))
|
|||
|
|
}
|