LeetCode Golang 5. 最長回文子串

5. 最長回文子串

給定一個字元串 

s

，找到 

s

 中最長的回文子串。你可以假設 

s

 的最大長度為 1000。

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。
      

示例 2：

輸入: "cbbd"
輸出: "bb"      

暴力解法: 列出子串, 求出符合條件的子串存入map, 篩選出最大值存入

func longestPalindrome(s string) string {
	if s == "" {
		return ""
	}
	if isPalindrome(s) {
		return s
	}

	pdMap := make(map[string]int)
	for i := 0; i < len(s); i++ {
		for j:=len(s);j>i+1;j--{
			tmp := s[i:j]
			//fmt.Println(tmp)
			if isPalindrome(tmp) {
				pdMap[tmp] = len(tmp)
			}
		}
	}
	max := 0
	rst := ""
	for k,v := range pdMap {
		if v > max {
			max = v
			rst = k
		}
	}
    if rst == "" {
		return s[0:1]
	}
	return rst
}

func isPalindrome(s string) bool {
	if len(s) < 1 {
		return false
	}
	if len(s) == 2 && s[0]==s[1]{
		return true
	}
	for i:=0;i<len(s)/2;i++{ // 3/2 = 1    4/2 = 2
		if s[i] != s[len(s)-i-1] {
			return false
		}
	}
	return true
}
      

　　

優化1: 因為題目隻要求 最長, 是以隻需要傳回最長的就可以了, 引入map實際上浪費了空間

package main

import "fmt"

//給定一個字元串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。
//
//示例 1：
//
//輸入: "babad"
//輸出: "bab"
//注意: "aba" 也是一個有效答案。
//示例 2：
//
//輸入: "cbbd"
//輸出: "bb"

func main() {
	s := "abb"
	fmt.Println(longestPalindrome(s))
}

func longestPalindrome(s string) string {
	if s == "" {
		return ""
	}
	if isPalindrome(s) || len(s) < 2 {
		return s
	}

	max := 0
	rst := ""
	
	for i := 0; i < len(s); i++ {
		for j:=len(s);j>i+1;j--{
			tmp := s[i:j]
			//fmt.Println(tmp)
			if isPalindrome(tmp) {
				if max < len(tmp) {
					max = len(tmp)
					rst = tmp
				}
			}
		}
	}
	
	if rst == "" {
		return s[0:1]
	}
	return rst
}

func isPalindrome(s string) bool {
	if len(s) < 1 {
		return false
	}
	if len(s) == 2 && s[0]==s[1]{
		return true
	}
	for i:=0;i<len(s)/2;i++{ // 3/2 = 1    4/2 = 2
		if s[i] != s[len(s)-i-1] {
			return false
		}
	}
	return true
}
      

大神解法:

func longestPalindrome(s string) string {
     if len(s) < 2 { // 肯定是回文，直接傳回
        return s
    }

    // 最長回文的首字元索引，和最長回文的長度
    begin, maxLen := 0, 1

    // 在 for 循環中
    // b 代表回文的**首**字元索引号，
    // e 代表回文的**尾**字元索引号，
    // i 代表回文`正中間段`首字元的索引号
    // 在每一次for循環中
    // 先從i開始，利用`正中間段`所有字元相同的特性，讓b，e分别指向`正中間段`的首尾
    // 再從`正中間段`向兩邊擴張，讓b，e分别指向此`正中間段`為中心的最長回文的首尾
    for i := 0; i < len(s); { // 以s[i]為`正中間段`首字元開始尋找最長回文。
        if len(s)-i <= maxLen/2 {
            // 因為i是回文`正中間段`首字元的索引号
            // 假設此時能找到的最長回文的長度為l, 則，l <= (len(s)-i)*2 - 1
            // 如果，len(s)-i <= maxLen/2 成立
            // 則，l <= maxLen - 1
            // 則，l < maxLen
            // 是以，無需再找下去了。
            break
        }

        b, e := i, i
        for e < len(s)-1 && s[e+1] == s[e] {
            e++
            // 循環結束後，s[b:e+1]是一串相同的字元串
        }

        // 下一個回文的`正中間段`的首字元隻會是s[e+1]
        // 為下一次循環做準備
        i = e + 1

        for e < len(s)-1 && b > 0 && s[e+1] == s[b-1] {
            e++
            b--
            // 循環結束後，s[b:e+1]是這次能找到的最長回文。
        }

        newLen := e + 1 - b
        // 創新記錄的話，就更新記錄
        if newLen > maxLen {
            begin = b
            maxLen = newLen
        }
    }

    return s[begin : begin+maxLen]

}
      

　　

這裡還有一些算法, 由leetCode官方提供:

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/

轉載于:https://www.cnblogs.com/gettolive/p/10191459.html