leetcode刷题心得 005: Longest Palindromic Substring (最长回文字符串)

题目地址: https://leetcode.com/problems/longest-palindromic-substring/

解题思路:

第一步:循环字符串,每次循环时, 判断当前字符前一位和后一位是否相等,如果相等,说明是回文。然后再判断前一位的前一位和后一位的后一位是否相等。。。如此找出当前字符能拼出的最长回文。如下代码就是这个逻辑。

for i:=0;i<len(s);{
        // b 回文开始的位置 e 回文结束的位置
        b,e :=i,i
        //判断当前字符前一位和后一位是否相等,如果相等,说明是回文。然后再判断前一位的前一位和后一位的后一位是否相等。。。  (回文判断核心逻辑) 
        for e<len(s)-1 && b>0 && s[e+1] == s[b-1]{
            b--
            e++
        }
        newLength := e+1-b
        if newLength >maxLength{
            begin = b
            maxLength = newLength
        }
        i++
    }

第二步,第一步的逻辑是能够处理 bab bacab 这类奇数位的回文的,但是不能判断出 baab baccab 这种偶数位回文。所以需要在逻辑中加入处理偶数位回文的过程

for i:=0;i<len(s);{
        b,e :=i,i
        //现在e还是在回文的中间字符位置,如果e的下一位和e相等,就把下一位也一起当作回文的中间字符,再下一位同理
        for e<len(s)-1 &&s[e]==s[e+1]{
            e++
        }
        
        i = e+1
        for e<len(s)-1 && b>0 && s[e+1] == s[b-1]{
            b--
            e++
        }
        
        newLength := e+1-b
        if newLength >maxLength{
            begin = b
            maxLength = newLength
        }
        
    }

第三步,上面已经把核心逻辑写完了,但是有一些特殊情况没处理。首先就是判断字符串长度,当已知字符串长度小于2时。(就只给了一个字符)那一定是个回文。 下面贴出完整的代码

func longestPalindrome(s string) string {
    if len(s) < 2 { 
		return s
	}
    begin,maxLength := 0,1
    
    for i:=0;i<len(s);{
        
        
        b,e :=i,i
        
        for e<len(s)-1 &&s[e]==s[e+1]{
            e++
        }
        
        i = e+1
        for e<len(s)-1 && b>0 && s[e+1] == s[b-1]{
            b--
            e++
        }
        
        newLength := e+1-b
        if newLength >maxLength{
            begin = b
            maxLength = newLength
        }
        
    }
    return s[begin:begin+maxLength]
}

OK~如有疑问,欢迎交流。

标签:golang leetcode

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章