Palindrome problems
1. Basic algorithm to check palindrome
This section presents methods for checking if a string is a palindrome:
- Basic Iterative Method: It uses a two-pointer approach to compare characters from both ends of the string.
- Recursive Approach: It reduces the problem to smaller substrings, checking the outer characters and recursively calling the function on the inner substring.
- Leetcode Problem 9: A specific application for checking if a number is a palindrome.
// Check if a string is palindrome or not
func isPalindromeBasic(str string) bool {
runes := []rune(str)
for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
if runes[i] != runes[j] {
return false
}
}
return true
}
func isPalindromeRecur(str string) bool {
// Base case: len = 0, 1
if len(str) == 0 || len(str) == 1 {
return true
}
// Recursion rule: check [0, [1, n-2], n-1] if s[0] == s[n-1]
if str[0] == str[len(str)-1] {
return isPalindromeRecur(str[1 : len(str)-1])
}
return false
}
// Leetcode 9 https://leetcode.com/problems/palindrome-number/
// Check if a number is palindrome(assume -123 is not)
func isPalindrome(x int) bool {
if x < 0 { return false }
str := strconv.Itoa(x)
for i := 0; i < len(str)/2; i++{
if str[i] != str[len(str)-1-i]{
return false
}
}
return true
}1.1 Check if a substring is palindrome at i and expand it.
This algorithm counts all palindromic substrings within a given string. It uses a central expansion technique, checking for palindromes centered at each character and between each pair of characters.
func CountTotalPalindromeSubstring() {
s := "aaa"
for i := 0; i < len(s); i++ {
CountExpand(s, i, i)
CountExpand(s, i, i+1)
}
}
func CountExpand(s string, left, right int) int {
count := 0
for left >= 0 && right < len(s) && s[left] == s[right] {
fmt.Printf("--substring is palindrom=%s\n", s[left:right+1])
count++
left-- // expand
right++
}
fmt.Printf("total count=%v\n", count)
return count
}
2. Check if a string can be palindrome if delete at most 1 char
This section tackles a variant of the palindrome problem (Leetcode 680) where the string may be modified by removing at most one character to form a palindrome. It uses a modified two-pointer approach.
// validPalindrome solves Leetcode 680 - easy
// https://leetcode.com/problems/valid-palindrome-ii/
//return true if the s can be palindrome after deleting at most one character from it.
func validPalindrome(s string) bool {
n := len(s)
if n == 0 { return true }
for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
if s[i] != s[j] {
return checkPalindrome(s, i+1, j) || checkPalindrome(s, i, j-1)
}
}
return true
}
// isPalindrome checks if s[i++,j--] is a palindrome
func checkPalindrome(s string, i, j int) bool {
for i < j {
if s[i] != s[j] {
return false
}
i++
j--
}
return true
}3. Check if a sentence is palindrome ignoring the case and non-alphanumeric chars
This algorithm (Leetcode 125) extends the palindrome check to sentences, ignoring non-alphanumeric characters and case differences.
// Valid Palindrome - Leetcode 125 - easy
// https://leetcode.com/problems/valid-palindrome/
func isSentencePalindrome(str string) bool {
low, high := 0, len(str)-1
for low < high {
for low < high && !isAlphanumeric(rune(str[low])) { low++ }
for low < high && !isAlphanumeric(rune(str[high])) { high-- }
if !equalIgnoreCase(str[low], str[high]) { return false }
low++
high--
}
return true
}
// equalIgnoreCase checks if two characters are equal, ignoring their case.
func equalIgnoreCase(x, y byte) bool {
return strings.ToLower(string(x)) == strings.ToLower(string(y))
}
// isAlphanumeric checks if a rune is alphanumeric.
func isAlphanumeric(r rune) bool {
return unicode.IsLetter(r) || unicode.IsNumber(r)
}4. longest palindrome substring, find the longest substring palindrome: at index i, expand i and check if s[left] == s[right].
It focuses on finding the longest palindromic substring within a given string (Leetcode 5). The algorithm uses central expansion from each character and pair of adjacent characters.
// 5. Longest Palindromic Substring: Given a string s, return the longest palindromic substring in s.
// https://leetcode.com/problems/longest-palindromic-substring/
func longestPalindrome(str string) string {
maxLen := 0
maxSubStr := ""
expand := func(left, right int) {
for left >= 0 && right < len(str) && str[left] == str[right] {
if maxLen < right-left+1 {
maxLen = right - left + 1
maxSubStr = str[left : right+1]
}
left-- // expand to two sides
right++
}
}
for i := 0; i < len(str); i++ {
expand(i, i)
}
for i := 0; i < len(str)-1; i++ {
expand(i, i+1)
}
fmt.Println("maxLen:", maxLen, "maxSubStr", maxSubStr)
return maxSubStr
} // Time: O(n), space O(1)5. Count number of substring palindrome
This algorithm (Leetcode 647) counts the number of palindromic substrings in a given string, similar to Section 1.1, but focuses on the count rather than expansion.
// countSubstrings solves Leetcode 647 - medium
// https://leetcode.com/problems/palindromic-substrings/
func countSubstrings(s string) int {
if len(s) <= 1 {
return len(s)
}
count := 0
for i := 0; i < len(s); i++ {
count += countPalindrome(s, i, i) // xxixx
count += countPalindrome(s, i, i+1) // xii+1xx
}
return count
} // O(n^2)
// Expand to further sides
func countPalindrome(s string, l, r int) int {
count := 0
for l >= 0 && r <= len(s)-1 && s[l] == s[r] {
fmt.Printf("panlidromes =%v\n", s[l:r+1]) // this prints all combinations
count++
l--
r++
}
return count
}6. Sub-sequence problem: find the longest subsequence palindrome.
This section deals with finding the longest palindromic subsequence in a string (Leetcode 516), a problem solved using dynamic programming.
// 516. Longest Palindromic Subsequence
// Given a string s, find the longest palindromic subsequence's length in s.
// https://leetcode.com/problems/longest-palindromic-subsequence/
func longestPalindromeSubseq(s string) int {
// dp[i][j]: max len between i and j in s
dp := make([][]int, len(s))
for i, _ := range dp {
dp[i] = make([]int, len(s))
}
for i := 0; i < len(s); i++ {
dp[i][i] = 1
}
for dis := 1; dis < len(s); dis++ {
for i := 0; i < len(s)-dis; i++ { //start
j := i + dis // end
// 1. a****a
if s[i] == s[j] {
dp[i][j] = 2 + dp[i+1][j-1]
} else {
// 2. ab****b or b***ba
dp[i][j] = max(dp[i][j-1], dp[i+1][j])
}
}
}
return dp[0][len(s)-1] // s[0:len(s)-1]
}6.2 A string is k-palindrome if it can be transformed into a palindrome by removing at most k characters from it.
// isValidPalindrome solves Leetcode 1216 - hard
// https://leetcode.com/problems/valid-palindrome-iii/
func isValidPalindrome(s string, k int) bool {
dp := make([][]int, len(s))
for i := 0; i < len(s); i++ {
dp[i] = make([]int, len(s))
}
for i := 0; i < len(s); i++ {
dp[i][i] = 1
}
for dis := 1; dis < len(s); dis++ {
for i := 0; i < len(s)-dis; i++ {
j := i + dis
if s[i] == s[j] {
dp[i][j] = 2 + dp[i+1][j-1]
} else {
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
}
}
}
return len(s)-dp[0][len(s)-1] <= k
}7. Palindrome with linked-list
Finally, here presents two methods (Leetcode 234) for checking if a linked list forms a palindrome:
- Using a Stack: It involves traversing the list with two pointers at different speeds and using a stack for comparison.
- Reversing the First Half: This method reverses the first half of the list during traversal and then compares it with the second half.
// isPalindrome solves Leetcode 234 - easy
// https://leetcode.com/problems/palindrome-linked-list/
func isPalindrome(head *ListNode) bool {
// 1 -> 2 -> 3 -> 2 -> 1 (odd)
//S0F0 S1 F1S2 S3 F2 F3 => if f.next != nil, slow=slow.next
// 1 -> 2 -> 3 -> 3 -> 2 -> 1 -->nil (even)
//SF S SF S F F (Good to slow)
if head == nil {
return true
}
stack := []int{}
slow, fast := head, head
for fast != nil && fast.Next != nil { //stops at last for odd, and nil for even
stack = append(stack, slow.Val) // stack = [1 2] for only 2 steps
slow = slow.Next // slow at 3(1-2, 2-3)
fast = fast.Next.Next
}
if fast != nil { // for odd case
slow = slow.Next
}
for slow != nil { // stops at nil
top := stack[len(stack)-1]
if top != slow.Val {
return false
}
stack = stack[:len(stack)-1]
slow = slow.Next
}
return true
}
// isPalindromeReverse solves leetcode 234 by reversing first half
// https://leetcode.com/problems/palindrome-linked-list/description/
func isPalindromeReverse(head *ListNode) bool {
if head == nil {
return true
}
var pre *ListNode = nil
slow, fast := head, head
for fast != nil && fast.Next != nil {
// let fast go first
fast = fast.Next.Next
next := slow.Next
slow.Next = pre
pre = slow
slow = next
}
if fast != nil {
slow = slow.Next
}
for slow != nil {
if pre.Val != slow.Val {
return false
}
pre = pre.Next
slow = slow.Next
}
return true
}