LeetCode 5. Longest Palindromic Substring

发表于 更新于 分类于 本文字数： 816 阅读时长 ≈ 1 分钟
LeetCode 5. Longest Palindromic Substring

5. Longest Palindromic Substring

Difficulty: Medium

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3
**Input:** "babad"
**Output:** "bab"
**Note:** "aba" is also a valid answer.

Example 2:

1
2
**Input:** "cbbd"
**Output:** "bb"

Solution

Language: Java

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
class Solution {
    int lo = 0, hi = 0, maxLen = 0;
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        for (int i = 0; i < s.length(); i++) {
            expand(s, i, i);
            expand(s, i, i + 1);
        }
        return s.substring(lo, hi + 1);
    }
    
    private void expand(String s, int i, int j) {
        while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
        }
        if (j - i - 1 > maxLen) {
            lo = i + 1;
            hi = j - 1;
            maxLen = j - i - 1;
        }
        
    }
}