LeetCode Python, Java, C++  >  动态规划  >  5. 最长回文子串  >  已支持 Ruby  >  LeetCode GitHub Code 或 转发

    力扣链接：5. 最长回文子串，难度等级：中等。

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

    • 回文性：如果字符串向前和向后读都相同，则它满足 回文性。
    • 子字符串 是字符串中连续的 非空 字符序列。

    示例 1:

    输入: s = "babad"

    输出: "bab"

    解释: "aba" 同样是符合题意的答案。

    示例 2:

    输入: s = "cbbd"

    输出: "bb"

    约束:

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

    How can we reuse a previously computed palindrome to compute a larger palindrome?

    提示 2

    If “aba” is a palindrome, is “xabax” a palindrome? Similarly is “xabay” a palindrome?

    提示 3

    Complexity based hint:
    If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation.

    思路
    上一题

    “动态规划”的模式

    “动态规划”，需要用dp数组来保存结果。dp[i][j]的值可以由它的前一个（或多个）值通过公式转化出来。因此，dp[i][j]值是一步一步推导出来的，它和先前的dp记录值都有联系。

    “动态规划”分为五步

    1. 确定数组dp的每个值代表的含义。
    2. 初始化数组dp的值。
    3. 根据一个示例，按顺序填入dp网格数据。
    4. 根据dp网格数据，推导出递推公式。
    5. 写出程序，并打印dp数组，不合预期就调整。

    细说这五步

    1. 确定数组dp的每个值代表的含义。
      • 先确定dp是一维数组还是二维数组。“一维滚动数组”意味着每次迭代时都会覆盖数组的值。大多时候，用“一维滚动数组”代替“二维数组”可以简化代码；但有些题目，比如要操作“两个位置可互换的数组”，为了理解方便，还是使用“二维数组”。
      • 尝试使用问题所求的返回值的含义作为 dp[i]（一维）或dp[i][j]（二维）的含义，约60%的概率能行。如果不行，再尝试其他含义。
      • 设计上尽量考虑保存更丰富的信息，重复信息只在某个dp[i]中保存一次就够了。
      • 使用简化的含义。如果用布尔值可以解决问题，就不要用数值。
    2. 初始化数组dp的值。dp的值涉及两个层面：
      1. dp的长度。通常是：条件数组长度加1或条件数组长度。
      2. dp[i]或dp[i][j]的值。dp[0]或dp[0][0]有时需要特殊处理。
    3. 根据一个示例，按顺序填入dp网格数据。
      • “递推公式”是“动态规划”算法的核心。但“递推公式”是隐晦的，想得到它，就需要制表，用数据启发自己。
      • 如果原示例不够好，需要自己重新设计一个。
      • 根据示例，填入dp网格数据，需要“按顺序”填，这是很重要的，因为它决定了代码的遍历顺序。
      • 大多时候，从左到右，从上到下。但有时需要从右向左、由下而上、从中间向右（或左），如“回文串”问题。有时，还需要一行遍历两次，先正向，再反向。
      • 当顺序决定对了，起点就决定好了，从起点出发，“按顺序”填写dp网格数据，这也是在模拟程序处理的过程。
      • 在此过程中，您将获得写出“递推公式”的灵感。如果您已经能推导出公式，不需要填完网格。
    4. 根据dp网格数据，推导出递推公式。
      • 有三个特别的位置需要注意： dp[i - 1][j - 1]、dp[i - 1][j]和dp[i][j - 1]，当前的 dp[i][j]往往取决于它们。
      • 操作“两个位置可互换的数组”时，因为对称性，我们可能需要同时使用dp[i - 1][j]和dp[i][j - 1]。
    5. 写出程序，并打印dp数组，不合预期就调整。
      • 重点分析那些不合预期的数值。

    读完了上面的内容，是不是感觉“动态规划”也没有那么难了？试着解出这道题吧。🤗

    复杂度

    时间复杂度

    空间复杂度

    Ruby # 

    # @param {String} s
# @return {String}
def longest_palindrome(s)
  longest = s[0]
  s = s.chars.join("#")

  s.size.times do |i|
    j = 1

    while j <= i and i + j < s.size
      break if s[i - j] != s[i + j]

      if s[i - j] == '#'
        j += 1
        next
      end

      length = j * 2 + 1

      if length > longest.size
        longest = s[i - j..i + j]
      end

      j += 1
    end
  end

  longest.gsub('#', '')
end

    其它语言

    欢迎贡献代码到 LeetCode Python GitHub -> 5. 最长回文子串。感谢！
    上一题