5.最长回文子串.md

5. 最长回文子串

url

题目

给你一个字符串 s，找到 s 中最长的回文子串。

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
输入：s = "cbbd"
输出："bb"
输入：s = "a"
输出："a"
输入：s = "ac"
输出："a"

方法

code

js

let longestPalindrome = s => {
    let expand = (s, l, r) => {
        while (l >= 0 && r < s.length && s[l] === s[r]) {
            l--;
            r++;
        }
        return r - l - 1;
    };
    if (s === null || s.length === 0)
        return s;
    let start = 0, end = 0, len1 = 0, len2 = 0, maxLen = 0;
    for (let i = 0; i < s.length; i ++) {
        len1 = expand(s, i - 1, i + 1);
        len2 = expand(s, i, i + 1);
        maxLen = Math.max(len1, len2);
        if (maxLen > (end - start)) {
            start = i - Math.floor((maxLen - 1) / 2);
            end = i + Math.floor(maxLen / 2);
        }
    }
    return s.substring(start, end + 1);
};

go

func longestPalindrome2(s string) string {
	if len(s) == 0 {
		return s
	}
	start, end := 0, 0
	len1, len2 := 0, 0
	maxLen := 0
	expand := func(s string, l int, r int) int {
		for l >= 0 && r < len(s) && s[l] == s[r] {
			l--
			r++
		}
		return r - l - 1
	}
	Max := func(a int, b int) int {
		if a < b {
			return b
		} else {
			return a
		}
	}
	for i := 0; i < len(s); i++ {
		len1 = expand(s, i - 1, i + 1)
		len2 = expand(s, i, i + 1)
		maxLen = Max(len1, len2)
		if maxLen > (end - start) {
			start = i - (maxLen - 1) / 2
			end = i + maxLen / 2
		}
	}
	return s[start : end + 1]
}

java

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0)
            return s;
        int start = 0, end = 0;
        int len1 = 0, len2 = 0;
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            len1 = expand(s, i - 1, i + 1);
            len2 = expand(s, i, i + 1);
            maxLen = Math.max(len1, len2);
            if (maxLen > (end - start)) {
                start = i - (maxLen - 1) / 2;
                end = i + maxLen / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    public int expand(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
            l--;
            r++;
        }
        return r - l -1;
    }
}