当前位置：网站首页>5. Longest Palindromic Substring

5. Longest Palindromic Substring

2022-08-03 16:38:00 【51CTO】

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

Example:

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

Example:

       
       Input: "cbbd"
       
Output: "bb"
      
1.
2.
3.

Java1:

       
       public class Solution {
       
    public String longestPalindrome(String s) {
       
        if (s.length() <= 1) return s;
       
        String res = "";
       
        for (int i = 0; i < s.length(); i++) {
       
            int l = i;
       
            int r = i;
       
            String tempStr = getStr(l, r, s);
       
            if (tempStr.length() > res.length()) {
       
                res = tempStr;
       
            }
       
            r = i + 1;
       
            tempStr = getStr(l, r, s);
       
            if (tempStr.length() > res.length()) {
       
                res = tempStr;
       
            }
       
        }
       
        return res;
       
    }
       
    public String getStr(int l, int r, String s) {        
       
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
       
            l --;
       
            r ++;
       
        }
       
        return s.substring(l + 1, r);
       
    }
       
}
      
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.
31.

Java2:

       
       class Solution {
       
    public String longestPalindrome(String s) {
       
        if (s.length() == 0) return new String();
       
        int min = 0, max = 1 ; 
       
        int idx = 1 , length = s.length(); 
       
        while (idx < length) {
       
            int [] even = longestPalindromeHelper(idx - 1, idx, s);
       
            int [] odd = longestPalindromeHelper(idx -1 , idx + 1, s);
       
            int [] v = (even[1] - even[0] > odd[1] - odd[0])? even: odd; 
       
            if (max - min < v[1] - v[0])
       
            {
       
                max = v[1];
       
                min = v[0];
       
            }
       
            idx ++; 
       
        }
       
        return s.substring(min, max);
       
    }
       
    private int [] longestPalindromeHelper(int left, int right, String s) {
       
        while (left>=0 && right < s.length() && s.charAt(left) == s.charAt(right)){
       
            left--; 
       
            right ++; 
       
        }
       
        return new int[]{left + 1, right};
       
    }
       
}
      
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.
31.
32.
33.
34.
35.
36.
37.
38.

JS:

       
       /**
       
 * @param {string} s
       
 * @return {string}
       
 */
       
var longestPalindrome = function(s) {
       
    if (s.length < 2) 
       
        return s;
       
    let result = '';
       
    for (let i = 0; i < s.length - 1; i++) {
       
        result = [result, expand(s, i, i), expand(s, i, i + 1)] 
       
        .reduce((pre, cur) => pre.length > cur.length ? pre : cur);
       
    } 
       
    return result;
       
}
       
function expand(str, left, right) {
       
    while (left >= 0 && right < str.length && str[left] === str[right]) {
       
        left--, right++;
       
    }
       
    return str.substring(left + 1, right);
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15740726/5540628

当前位置：网站首页>5. Longest Palindromic Substring

5. Longest Palindromic Substring

边栏推荐

猜你喜欢

随机推荐