动态规划

字符串

  • 最长回文子串

    难度：中等

    给你一个字符串 s，找到 s 中最长的回文子串。
    示例 1：
    输入：s = “babad”
    输出：”bab”
    解释：”aba” 同样是符合题意的答案。

    示例 2：
    输入：s = “cbbd”
    输出：”bb”

  • 方法一

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution(object):
      def longestPalindrome(self, s):
          """
          :type s: str
          :rtype: str
          """
          n = len(s)
          maxlen=1
          be=0
          def ishw(s,i,j):
              while(i<j):
                  if s[i]!=s[j]:
                      return False
                  i+=1
                  j-=1
              return True
          if n <=1:
              return s
          for i in range(n):
              for j in range(i,n):
                  if j-i+1>maxlen and ishw(s,i,j):
                      maxlen=j-i+1
                      be=i
          return s[be:be+maxlen]

    解析

    复杂度分析
    时间复杂度：O(n^2)，其中 n 是字符串的长度。动态规划的状态总数为 O(n^2)，对于每个状态，我们需要转移的时间为 O(1)。
    空间复杂度：O(n^2)，即存储动态规划状态需要的空间。