Count number of palindromes within a string

  • A+
Category:Languages

I have written the below code to count the number of palindromic strings in a given string:

countPalindromes <- function(str){   len <- nchar(str)   count <- 0    for(i in 1:len){     for(j in i:len){         subs <- substr(str, i, j)         rev <- paste(rev(substring(subs, 1:nchar(subs), 1:nchar(subs))), collapse = "")         if(subs == rev){           count <- count + 1         }       }   }   count } 

This is actually working fine but the code needs to be optimized in such a way so that it executes at a faster rate.

Please suggest some ways to optimize this piece of code.

 


Here's a solution that uses the wonderful stringi package - just as Andre suggested - together with a wee bit of vectorization.

cp <- function(s) {   lenstr <- stri_length(s)  # Get the length   res <- sapply(1:lenstr, function(i) {     # Get all substrings     sub_string <- stringi::stri_sub(s, i, i:lenstr)     # Count matches     sum((sub_string == stringi::stri_reverse(sub_string)))   })   sum(res) } 

This should give the same result as your function

> cp("enafdemderredmedfane") [1] 30 > countPalindromes("enafdemderredmedfane") [1] 30 

There is not much speedup for short strings, but for longer strings you can really see a benefit:

> microbenchmark::microbenchmark(countPalindromes("howdoyoudo"), cp("howdoyoudo")) Unit: microseconds                            expr     min       lq     mean   median      uq     max neval cld  countPalindromes("howdoyoudo") 480.979 489.6180 508.9044 494.9005 511.201 662.605   100   b                cp("howdoyoudo") 156.117 163.1555 175.4785 169.5640 179.993 324.145   100  a  

Compared to

> microbenchmark::microbenchmark(countPalindromes("enafdemderredmedfane"), cp("enafdemderredmedfane")) Unit: microseconds                                      expr      min        lq      mean   median       uq      max neval cld  countPalindromes("enafdemderredmedfane") 2031.565 2115.0305 2475.5974 2222.354 2384.151 6696.484   100   b                cp("enafdemderredmedfane")  324.991  357.6055  430.8334  387.242  478.183 1298.390   100  a  

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: