力扣00005.最长回文子串

发表于 分类于 阅读次数： 本文字数： 2.6k 阅读时长 ≈ 9 分钟
最长回文子串、字符串、动态规划、中等

题目描述

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

示例 2：

输入：s = “cbbd”
输出：”bb”

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

解决方法

C++

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
class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) {
            return "";
        }
        int n = s.length();
        int start = 0, max_length = 1;
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for (int i = 0; i < n; ++i) {
            dp[i][i] = true;
        }
        for (int i = 0; i < n - 1; ++i) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = true;
                start = i;
                max_length = 2;
            }
        }
        for (int length = 3; length <= n; ++length) {
            for (int i = 0; i <= n - length; ++i) {
                int j = i + length - 1;
                if (s[i] == s[j] && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    start = i;
                    max_length = length;
                }
            }
        }
        return s.substr(start, max_length);
    }
};

结果

执行用时 : 188 ms, 击败 50.83% 使用 C++ 的用户

内存消耗 : 22.71 MB, 击败 52.86% 使用 C++ 的用户

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
public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

结果

执行用时 : 16 ms, 击败 87.41% 使用 Java 的用户

内存消耗 : 41.15 MB, 击败 71.32% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def longestPalindrome(self, s):
        if not s:
            return ""
        n = len(s)
        start, max_length = 0, 1
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                start = i
                max_length = 2
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    start = i
                    max_length = length
        return s[start:start + max_length]

结果

执行用时 : 2744 ms, 击败 50.76% 使用 Python 的用户

内存消耗 : 20.48 MB, 击败 33.90% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        n = len(s)
        start, max_length = 0, 1
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                start = i
                max_length = 2
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    start = i
                    max_length = length
        return s[start:start + max_length]

结果

执行用时 : 1988 ms, 击败 58.06% 使用 Python3 的用户

内存消耗 : 25.75 MB, 击败 5.00% 使用 Python3 的用户

C

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
char* longestPalindrome(char* s) {
    if (s == NULL || *s == '\0') {
        return "";
    }
    int n = strlen(s);
    int start = 0, max_length = 1;
    int dp[n][n];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; ++i) {
        dp[i][i] = 1;
    }
    for (int i = 0; i < n - 1; ++i) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = 1;
            start = i;
            max_length = 2;
        }
    }
    for (int length = 3; length <= n; ++length) {
        for (int i = 0; i <= n - length; ++i) {
            int j = i + length - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = 1;
                start = i;
                max_length = length;
            }
        }
    }
    char* result = (char*)malloc((max_length + 1) * sizeof(char));
    strncpy(result, s + start, max_length);
    result[max_length] = '\0';
    return result;
}

结果

执行用时 : 112 ms, 击败 35.91% 使用 C 的用户

内存消耗 : 11.07 MB, 击败 8.11% 使用 C 的用户

C#

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
public class Solution {
    public string LongestPalindrome(string s) {
        if (string.IsNullOrEmpty(s)) {
            return "";
        }
        int n = s.Length;
        int start = 0, maxLength = 1;
        bool[,] dp = new bool[n, n];
        for (int i = 0; i < n; i++) {
            dp[i, i] = true;
        }
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == s[i + 1]) {
                dp[i, i + 1] = true;
                start = i;
                maxLength = 2;
            }
        }
        for (int length = 3; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (s[i] == s[j] && dp[i + 1, j - 1]) {
                    dp[i, j] = true;
                    start = i;
                    maxLength = length;
                }
            }
        }
        return s.Substring(start, maxLength);
    }
}

结果

执行用时 : 104 ms, 击败 62.37% 使用 C# 的用户

内存消耗 : 42.81 MB, 击败 39.55% 使用 C# 的用户

JavaScript

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
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if (!s || s.length === 0) {
        return "";
    }
    let n = s.length;
    let start = 0;
    let maxLength = 1;
    let dp = Array.from(Array(n), () => new Array(n).fill(false));
    for (let i = 0; i < n; i++) {
        dp[i][i] = true;
    }
    for (let i = 0; i < n - 1; i++) {
        if (s[i] === s[i + 1]) {
            dp[i][i + 1] = true;
            start = i;
            maxLength = 2;
        }
    }
    for (let length = 3; length <= n; length++) {
        for (let i = 0; i <= n - length; i++) {
            let j = i + length - 1;
            if (s[i] === s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                start = i;
                maxLength = length;
            }
        }
    }
    return s.substring(start, start + maxLength);
};

结果

执行用时 : 608 ms, 击败 25.61% 使用 JavaScript 的用户

内存消耗 : 70.17 MB, 击败 14.82% 使用 JavaScript 的用户

TypeScript

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
function longestPalindrome(s: string): string {
    if (!s || s.length === 0) {
        return "";
    }
    const n = s.length;
    let start = 0;
    let maxLength = 1;
    const dp: boolean[][] = Array.from(Array(n), () => new Array(n).fill(false));
    for (let i = 0; i < n; i++) {
        dp[i][i] = true;
    }
    for (let i = 0; i < n - 1; i++) {
        if (s[i] === s[i + 1]) {
            dp[i][i + 1] = true;
            start = i;
            maxLength = 2;
        }
    }
    for (let length = 3; length <= n; length++) {
        for (let i = 0; i <= n - length; i++) {
            const j = i + length - 1;
            if (s[i] === s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                start = i;
                maxLength = length;
            }
        }
    }
    return s.substring(start, start + maxLength);
}

结果

执行用时 : 676 ms, 击败 24.04% 使用 TypeScript 的用户

内存消耗 : 71.98 MB, 击败 17.54% 使用 TypeScript 的用户

PHP

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
class Solution {

    /**
     * @param String $s
     * @return String
     */
    function longestPalindrome($s) {
        if (empty($s)) {
            return "";
        }
        $n = strlen($s);
        $start = 0;
        $maxLength = 1;
        $dp = array_fill(0, $n, array_fill(0, $n, false));
        for ($i = 0; $i < $n; $i++) {
            $dp[$i][$i] = true;
        }
        for ($i = 0; $i < $n - 1; $i++) {
            if ($s[$i] == $s[$i + 1]) {
                $dp[$i][$i + 1] = true;
                $start = $i;
                $maxLength = 2;
            }
        }
        for ($length = 3; $length <= $n; $length++) {
            for ($i = 0; $i <= $n - $length; $i++) {
                $j = $i + $length - 1;
                if ($s[$i] == $s[$j] && $dp[$i + 1][$j - 1]) {
                    $dp[$i][$j] = true;
                    $start = $i;
                    $maxLength = $length;
                }
            }
        }
        return substr($s, $start, $maxLength);
    }
}

结果

执行用时 : 1048 ms, 击败 36.36% 使用 PHP 的用户

内存消耗 : 37.88 MB, 击败 36.36% 使用 PHP 的用户

Swift

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
class Solution {
    func longestPalindrome(_ s: String) -> String {
        if s.isEmpty {
            return ""
        }
        let chars = Array(s)
        var start = 0, end = 0
        for i in 0..<chars.count {
            let len1 = expandAroundCenter(chars, i, i)
            let len2 = expandAroundCenter(chars, i, i + 1)
            let len = max(len1, len2)
            if len > end - start {
                start = i - (len - 1) / 2
                end = i + len / 2
            }
        }
        return String(chars[start...end])
    }
    func expandAroundCenter(_ chars: [Character], _ left: Int, _ right: Int) -> Int {
        var left = left, right = right
        while left >= 0 && right < chars.count && chars[left] == chars[right] {
            left -= 1
            right += 1
        }
        return right - left - 1
    }
}

结果

执行用时 : 24 ms, 击败 76.19% 使用 Swift 的用户

内存消耗 : 15.47 MB, 击败 5.71% 使用 Swift 的用户

Kotlin

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
class Solution {
    fun longestPalindrome(s: String): String {
        if (s.isEmpty()) {
            return ""
        }
        val n = s.length
        var start = 0
        var maxLength = 1
        val dp = Array(n) { BooleanArray(n) }
        for (i in 0 until n) {
            dp[i][i] = true
        }
        for (i in 0 until n - 1) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = true
                start = i
                maxLength = 2
            }
        }
        for (length in 3..n) {
            for (i in 0 until n - length + 1) {
                val j = i + length - 1
                if (s[i] == s[j] && dp[i + 1][j - 1]) {
                    dp[i][j] = true
                    start = i
                    maxLength = length
                }
            }
        }
        return s.substring(start, start + maxLength)
    }
}

结果

执行用时 : 268 ms, 击败 59.81% 使用 Kotlin 的用户

内存消耗 : 37.95 MB, 击败 23.36% 使用 Kotlin 的用户

Dart

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
import 'dart:math';

class Solution {
  String longestPalindrome(String s) {
    if (s.isEmpty) {
      return "";
    }
    int start = 0;
    int maxLen = 1;
    for (int i = 0; i < s.length; i++) {
      int len1 = expandAroundCenter(s, i, i);
      int len2 = expandAroundCenter(s, i, i + 1);
      int len = max(len1, len2);
      if (len > maxLen) {
        maxLen = len;
        start = i - (maxLen - 1) ~/ 2;
      }
    }
    return s.substring(start, start + maxLen);
  }
  int expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length && s[left] == s[right]) {
      left--;
      right++;
    }
    return right - left - 1;
  }
}

结果

执行用时 : 280 ms, 击败 100.00% 使用 Dart 的用户

内存消耗 : 141.77 MB, 击败 100.00% 使用 Dart 的用户

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 {
    if len(s) == 0 {
        return ""
    }
    var start, end int
    for i := 0; i < len(s); i++ {
        len1 := expandAroundCenter(s, i, i)
        len2 := expandAroundCenter(s, i, i+1)
        length := max(len1, len2)

        if length > end-start {
            start = i - (length-1)/2
            end = i + length/2
        }
    }
    return s[start : end+1]
}
func expandAroundCenter(s string, left, right int) int {
    for left >= 0 && right < len(s) && s[left] == s[right] {
        left--
        right++
    }
    return right - left - 1
}
func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Go 的用户

内存消耗 : 2.34 MB, 击败 65.18% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# @param {String} s
# @return {String}
def longest_palindrome(s)
    return "" if s.nil? || s.empty?
    start = 0
    max_len = 1
    (0...s.length).each do |i|
        len1 = expand_around_center(s, i, i)
        len2 = expand_around_center(s, i, i + 1)
        len = [len1, len2].max
        if len > max_len
            max_len = len
            start = i - (max_len - 1) / 2
        end
    end
    s[start...(start + max_len)]
end
def expand_around_center(s, left, right)
    while left >= 0 && right < s.length && s[left] == s[right]
        left -= 1
        right += 1
    end
    right - left - 1
end

结果

执行用时 : 620 ms, 击败 83.33% 使用 Ruby 的用户

内存消耗 : 206.72 MB, 击败 16.67% 使用 Ruby 的用户

Scala

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
object Solution {
  def longestPalindrome(s: String): String = {
    if (s.isEmpty) return ""
    var start = 0
    var end = 0
    def expandAroundCenter(left: Int, right: Int): Int = {
      var l = left
      var r = right
      while (l >= 0 && r < s.length && s.charAt(l) == s.charAt(r)) {
        l -= 1
        r += 1
      }
      r - l - 1
    }
    for (i <- 0 until s.length) {
      val len1 = expandAroundCenter(i, i)
      val len2 = expandAroundCenter(i, i + 1)
      val len = Math.max(len1, len2)
      if (len > end - start) {
        start = i - (len - 1) / 2
        end = i + len / 2
      }
    }
    s.substring(start, end + 1)
  }
}

结果

执行用时 : 600 ms, 击败 76.92% 使用 Scala 的用户

内存消耗 : 54.00 MB, 击败 100.00% 使用 Scala 的用户

Rust

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
impl Solution {
    pub fn longest_palindrome(s: String) -> String {
        let n = s.len();
        let s: Vec<char> = s.chars().collect();
        let mut dp = vec![vec![false; n]; n];
        let mut start = 0;
        let mut max_len = 1;
        for i in 0..n {
            dp[i][i] = true;
        }
        for i in 0..n - 1 {
            if s[i] == s[i + 1] {
                dp[i][i + 1] = true;
                start = i;
                max_len = 2;
            }
        }
        for k in 3..=n {
            for i in 0..=n - k {
                let j = i + k - 1;
                if s[i] == s[j] && dp[i + 1][j - 1] {
                    dp[i][j] = true;
                    if k > max_len {
                        start = i;
                        max_len = k;
                    }
                }
            }
        }
        s[start..start + max_len].iter().collect::<String>()
    }
}

结果

执行用时 : 52 ms, 击败 58.62% 使用 Rust 的用户

内存消耗 : 3.30 MB, 击败 5.17% 使用 Rust 的用户

Racket

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(define/contract (longest-palindrome s)
  (-> string? string?)
    (longest-palindrome/center-better s)
  )
(define (longest-palindrome/center-better s)
  (define (palindrome/in s n/begin n/end)
    (if (and (>= n/begin 0) (< n/end (string-length s)))
        (if (char=? (string-ref s n/begin) (string-ref s n/end))
            (palindrome/in s (sub1 n/begin) (add1 n/end))
            (list (add1 n/begin) (sub1 n/end)))
        (list (add1 n/begin) (sub1 n/end))))
  (define (palindrome/center s n/begin n/end n)
    (if (>= n (string-length s))
        (substring s n/begin (add1 n/end))
        (match-let ([(list begin1 end1) (palindrome/in s n n)]
                    [(list begin2 end2) (palindrome/in s n (add1 n))])
          (cond 
            [(> (- end2 begin2) (- n/end n/begin)) (palindrome/center s begin2 end2 (add1 n))]
            [(> (- end1 begin1) (- n/end n/begin)) (palindrome/center s begin1 end1 (add1 n))]
            [else (palindrome/center s n/begin n/end (add1 n))]))))
  (palindrome/center s 0 0 0))

结果

执行用时 : 236 ms, 击败 100.00% 使用 Racket 的用户

内存消耗 : 99.04 MB, 击败 100.00% 使用 Racket 的用户

Erlang

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
-spec longest_palindrome(S :: unicode:unicode_binary()) -> unicode:unicode_binary().
longest_palindrome(S) ->
    list_to_binary(main(binary_to_list(S))).
main(S) ->
    {FromZeroString, FromZeroLength} = loop(S, get_zero_list(S), 0),
    {FromOneString, FromOneLength} = loop(S, get_one_list(S), 1),
    Longer = FromZeroLength > FromOneLength,
    if
        Longer ->
            substr(FromZeroString, FromZeroLength);
        true ->
            substr(FromOneString, FromOneLength)
    end.
loop(S, [ResultHead|ResultTail], N) ->
    NextList = next_list(S, ResultTail),
    CheckListResult = check_list(NextList),
    if
        CheckListResult ->
            loop(S, NextList, N + 2);
        true ->
            {find_first(S, [ResultHead|ResultTail]), N}
    end.
substr(_, N) when N == 0 ->
    [];
substr([Head|Tail], N) ->
    [Head|substr(Tail, N - 1)].
get_zero_list([Head|Tail]) ->
    [{true, [Head|Tail]} | get_zero_list(Tail)];
get_zero_list([]) ->
    [].
get_one_list([_ | Tail]) ->
    [{true, Tail} | get_one_list(Tail)];
get_one_list([]) ->
    [].
next_list([Head1|Tail1], [{IsPalindrome, [Head2|Tail2]} | ResultTail]) ->
    [{(Head1 == Head2) and IsPalindrome, Tail2} | next_list(Tail1, ResultTail)];
next_list(_, [{_, []}]) ->
    [];
next_list(_, []) ->
    [].
check_list(S) ->
    check_list(S, false).
check_list([{IsPalindrome, _} | Tail], Result) ->
    check_list(Tail, IsPalindrome or Result);
check_list([], Result) ->
    Result.
find_first([Head1|Tail1], [{IsPalindrome, _} | Tail2]) ->
    if
        IsPalindrome ->
            [Head1|Tail1];
        true ->
            find_first(Tail1, Tail2)
    end;
find_first(_, []) ->
    "".

结果

执行用时 : 516 ms, 击败 100.00% 使用 Erlang 的用户

内存消耗 : 57.55 MB, 击败 100.00% 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户