Ruby - 查找字符串中最长的回文子串

Question

我知道如何判断一个字符串是否是回文

string1 == string1.reverse

虽然字符串中有多个回文，但有点困难

"abcdxyzyxabcdaaa"

上述字符串中，长度大于1的回文有4个

"xyzyx", "yzy", "aaa" and "aa"

在这种情况下，最长的回文是“xyxyx”，长度为 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

Answer 1

如果您只是寻找最大的回文子串，这里有一个快速但粗略的解决方案。

def longest_palindrome(string, size)
  string.size.times do |start| # loop over the size of the string
    break if start + size > string.size # bounds check

    reverse = string[start, size].reverse

    if string.include? reverse #look for palindrome
      return reverse #return the largest palindrome
    end
  end
  longest_palindrome(string, size - 1) # Palindrome not found, lets look for the next smallest size 
end