我知道如何判断一个字符串是否为回文
string1 == string1.reverse
但在一个字符串中有多个回文时会有点困难
"abcdxyzyxabcdaaa"
在上面的字符串中,有4个回文长度大于1
"xyzyx", "yzy", "aaa" and "aa"
在本例中,最长的回文是“xyxy”,有5个字符长。
我该如何着手解决这个问题呢?
我知道array#combination方法,但在本例中不起作用。
我在考虑实施这样的计划
def longest_palindrome(string)
palindromes = []
for i in 2..string.length-1
string.chars.each_cons(i).each {|x|palindromes.push(x) if x == x.reverse}
end
palindromes.map(&:join).max_by(&:length)
end
6条答案
按热度按时间r8uurelv1#
如果你只是寻找最大的回文子串,这里有一个快速和肮脏的解决方案.
mjqavswn2#
切片方法对于解决这个问题很方便。用经典的双while循环方法测试每个子字符串,其中
(i, j)
分别表示子字符串的起始索引和长度。String#slice方法的工作方式如下:
piah890a3#
这个函数检查整个字符串
str
是否是回文,如果是,我们就完成了;如果不是,则检查所有长度为str.size-1
的子串,如果有一个是回文,则结束;如果不是,则检查长度为str.size-1
子串,依此类推。这里的关键方法是Enumerable#each_cons。
9fkzdhlc4#
最长回文子串:复杂度O(n)**
随附基准
8wigbo565#
下面是另一个解决方案,使用较少的Ruby特性和迭代代替递归:
svujldwt6#
这是wikipedia中提出的幼稚/缓慢解决方案的一个Ruby实现
这是马纳彻的算法
关于如何用Ruby的方式来做有什么建议吗?