回文计数(字符串)

Question

因此，我今天研究了www.hackerearth.com，并用ruby：http://www.hackerearth.com/problem/algorithm/palindrome-count-1/解决了我的第一个问题陈述。

回文计数问题

给定字符串S，计数非空子字符串的数量，这些子字符串是回文。子字符串是字符串中任何连续的字符序列。如果字符串的反向与其本身相同，则称字符串为回文。如果两个子字符串发生在S中不同的位置，则它们是不同的。

输入：输入只包含一行，其中包含字符串S。

Output：打印一个数字，即回文子字符串的数量。

约束

1 <= _S_s_

S只包含小写拉丁字母，即a到z字符。

示例输入(明文链接)：dskjkd

示例输出(明文链接)：7

解释-

这7个子字符串是d，s，k，j，k，d，kjk。

时间限制3秒

内存限制256 MB

源限制1024 KB

，这就是我所做的：

chars = gets.chomp.gsub(' ', '').split('')
counts = chars.count
(2..chars.count).each do |len|
  chars.combination(len).each do |comb|
    string = comb.inject(:<<)
    counts += 1 if string.reverse == string
  end
end
puts counts

但是，这种方法在执行时间和内存使用方面似乎效率低下。有什么方法可以优化这个吗？或者有任何其他方法来解决这个问题，算法也是受欢迎的解决方案！谢谢。

编辑

因为所有的答案都是正确的。我不得不选择一个有效率的。因此，我运行了基准测试，结果如下：https://gist.github.com/suryart/7577481

根据结果，您可以看到这个答案要快得多。谢谢你的新方法/解决方案！:)

Answer 1

使用该算法从用Ruby分割字符串以获得所有子字符串的最佳方法是什么？中获取字符串的所有子集

count = 0

(0..len-1).each do |i|
  (i..len-1).each do |j|
    temp = s[i..j]
    count = count + 1 if temp == temp.reverse
  end
end
puts "found #{count} palindromes"

Answer 2

这种方法--在伪代码中--应该有效。

input: String s

// each single letter is palindrome itself
palindromsCount = length(s)

// let count all odd-length palindromes first (palindrome of length 1 already counted)
// we will be checking from the very middle of a sub-string, if it is symmetric 
for(int i = 1; i < length(s)-1; i++)
   for(int j = 1; ; j++)
       if (i - j < 0 || i + j >= length(s) || s[i-j] != s[i+j])
          break
       else
          palindromsCount += 1

// let count in similar way all even-length palindromes
for(int i = 0; i < length(s)-1; i++)
   for(int j = 0; ; j++)
       if (i - j < 0 || i + j + 1 >= length(s) || s[i-j] != s[i+j+1])
          break
       else
          palindromsCount += 1

当然，编辑可以组合成一个循环--我不想为了更好的可读性而这么做。

Answer 3

缺点在这里很方便：

str = "momanddadpaddledthekayak"

b = str.chars
(1..b.size).reduce(0) {|t,n| t + b.each_cons(n).reduce(0) \
  {|r,e| w = e.join; w==w.reverse ? r + 1 : r}} # => 30

如果我们想看到掌纹：

b = str.chars
pals = (1..b.size).each_with_object([]) {|n, a| b.each_cons(n).each \
  {|e| w = e.join; a << w if w==w.reverse}}

p pals.size # => 30
p pals #  => ["m", "o", "m", "a", "n", "d", "d", "a", "d", "p", "a",\
              "d", "d", "l", "e", "d", "t", "h", "e", "k", "a", "y",
              "a", "k", "dd", "dd", "mom", "dad", "aya", "kayak"] 

编辑：@squi家伙做了一个有用的观察，我们可能不想计算重复数。如果是这样的话，我上面的第一次计算将无法使用，而第二次计算必须如squiguy建议的那样(例如，p a.uniq.size)进行更改，或者修改以构建散列，而不是数组：

b = str.chars
pals = (1..b.size).each_with_object({}) {|n,h| b.each_cons(n).each \
  {|e| w = e.join; h[w] = 0 if w==w.reverse}}.keys

p pals.size # => 17
p pals# => ["m", "o", "a", "n", "d", "p", "l", "e", "t",\
            "h", "k", "y", "dd", "mom", "dad", "aya", "kayak"] 

编辑:将each替换为each_with_object。在重读这个问题时，似乎要计算出欺骗。