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. 递归的力量（二）