5. Longest Palindromic Substring

寻找一个字符串中是回文的最长子字符串

遍历字符串，计算以每个字符为中心的回文字符串的长度并比较,注意以一个字母为中心的回文有两种情况，例如aba和abba两个回文都以b为中心

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # 5 star        
        rs = ""
        for index, char in enumerate(s):
        	rs = max(self.get_len(s,index, index), self.get_len(s, index, index+1), rs, key=len)
        return rs

    # 这个解法非常巧妙， 从一个字符向左右扩展，直到左右不相等
    def get_len(self, s, l, r):
    	while l >= 0 and r < len(s) and s[l] == s[r]:
    		l -= 1
    		r += 1
    	return s[l+1:r]

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

func longestPalindrome(s string) string {
	var ret1, ret2, maxByte, current string
	for index, _ := range s {
		ret1 = getLength(s, index, index)
		ret2 = getLength(s, index, index+1)
		if len(ret1) > len(ret2) {
			current = ret1
		} else {
			current = ret2
		}

		if len(current) > len(maxByte) {maxByte = current}
	}
	return string(maxByte)
}

// 核心是这个函数，left和right两个索引不断比较它们的值是否相同，如果相同就继续向两边扩展
func getLength(s string, left int, right int) string {
	for left >= 0 && right < len(s) {
		if s[left] == s[right] {
			left -= 1
			right += 1
		} else {
			break
		}

	}
	return s[left+1:right]
}