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