402's Dojo

LeetCode实战 - Longest Palindromic Substring

最近在刷leetcode,对自己的算法思路做个简单的记录,希望最后回顾起来自己是有提高的。

通篇算法都是用Ruby语言实现,文内不再赘述。Markdown没有支持数学格式,所以时间复杂度的记法比较粗糙,见谅。

这一系列的文章可以在这里找到。


本期题目:

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
题目难度: Medium
中文翻译:在一个给定的字符串S中找到最长的回文子串。为了解题方便假定字符串长度不超过1000,有且只有一个最长回文子串。

多些时间可以少些Code

回文问题首先想到的是利用递归和栈数据结构。
先来说递归。递归的主要目的是简化实现,将当前问题转化为规模更小的问题。实现递归的流程如下:

  1. 确认是否适用递归?即问题是否可以分解为形式相同但规模更小的问题?如果存在这样一种分解,那么这种分解是否存在一种简单情境?
  2. 找到这种简单实现,作为递归的出口;
  3. 实现问题分解的代码,作为递归的主体。
    所以针对回文查找的简单实现如下:
    def ispalinderme(str)
    if str.length == 0 || str.length == 1 then
    return 1
    else
    return (str[0] == str[str.length-1]) ? ispalinderme(str[1, str.length-2]) : 0
    end
    end
    那么,如何实现在给定字符串中找到最长的回文子串呢?

还是要Code

参考资料

  1. 递归的力量(二)

评论