Problem
Write a function that, given an input string, locates and returns the longest sequence in the string that is a palindrome.
Solution
Every sub-string starting from the longest to the shortest needs to checked as shown below
bool is_palindrome(string const& str, size_t i,size_t n); string max_sub_palindrome(string const& str) { size_t N = str.length(); for(size_t n=N; n>0; --n) { for (size_t i=0; i+n <=N; ++i) if (is_palindrome(str,i,n)) return str.substr(i,n); } return string(); }
is_palindrome
can be computed recursively as shown below
bool is_palindrome(string const& str, size_t i,size_t n) { if (n<=1) return true; else return str[i]==str[i+n-1] && is_palindrome(str,i+1,n-2); }
The above implementation of is_palindrome
has O(n) time complexity.
Thus max_sub_palindrome
has O(N3) time complexity where N is the length of the string. Notice however that is_palindrome
is can be memoised as follows:
class Search { public: Search(size_t n):N(n),arr(n*n) { } bool operator() (string const& str, size_t i,size_t n) { if (n<=1) return true; else if (Get(i,n)) return false; else if( str[i]==str[i+n-1]) { auto k = operator()(str,i+1,n-2); if (k) return k; else { Set(i,n); return k; } } else { Set(i,n); return false; } } private: bool Get (size_t i, size_t j) { return arr[i*N+j-1]; } void Set (size_t i, size_t j) { arr[i*N+j-1]=true; std::cout<<i<<","<<j<<std::endl; } std::vector<bool> arr; size_t N; };
I would like to draw your attention to Line 19 and Line 25, where we flag that the sub-string commencing at i
of length n
is not a palindrome. We make use of that fact in Line 10 so as to avoid calling the operator() recursively if the specific problem has already been visited. We could have implemented the class as a closure in any language that supports it, which is almost all languages except C/C++.
The main function is same, save for the marked line as shown below:
string max_sub_palindrome(string const& str) { size_t N = str.length(); Search is_palindrome(N); ///<---added for(size_t n=N; n>0; --n) { for (size_t i=0; i+n <=N; ++i) { if(is_palindrome(str,i,n)) return str.substr(i,n); } } return std::string(); }
Can use Dynamic Programming. Very similar to matrix multiplication using DP algorithm.
DP and memoisation are very different. See https://stackoverflow.com/questions/6184869/what-is-the-difference-between-memoization-and-dynamic-programming#6185005