0

Possible Duplicate:
Algorithm to find palindromes

How do I find all palindromes in a string like:

"AA BB AA TTT AA BB"

I know how to find palindromes in a single string and if I merge these strings by removing the " " character, I can still find the palindromes...but if I do so, how do I reconstruct the original words....

Or is there any other approach which may take less time...Any clue..?

Community
  • 1
  • 1
ASingh
  • 475
  • 1
  • 13
  • 24
  • I don't understand "find all palindromes". Isn't a string either a palindrome or not? – Lee Meador Jan 18 '13 at 19:47
  • 3
    What do you mean by _how do I reconstruct the original words...._? – Smit Jan 18 '13 at 19:50
  • i don't understand you very but you can try this http://stackoverflow.com/questions/1115001/write-a-function-that-returns-the-longest-palindrome-in-a-given-string – Splinky Jan 18 '13 at 19:50
  • @LeeMeador: I think he means "all substrings that are palindromes" – AndyG Jan 18 '13 at 20:02
  • Maybe you can find some clue from this post:http://stackoverflow.com/questions/10468208/manachers-algorithm-algorithm-to-find-longest-palindrome-substring-in-linear-t. – taocp Jan 18 '13 at 20:14

3 Answers3

4

EDIT: I'm assuming that what you're asking is this: Given a string of characters, how do I determine all possible substrings that are palindromes?

You can build up from single characters, which are trivially palindromes of themselves, then consider all substrings of length 2, and then all substrings of length 3.

Fortunately, a palindome has the recursive relationship such that if you removed the first and last letters, you must still have a palindrome. Therefore, if a string of length 4 is a palindrome (Like ABBA), then the substring with the first and last characters removed ('BB') must also be a palindrome.

Consider a dynamic programming solution to compute this for any given string, as the recursive relationship defined above satisfies the optimal subproblems requirement for DP.

AndyG
  • 39,700
  • 8
  • 109
  • 143
0

The problem really reduces down to finding all substrings. After you've gone through each "word" in your string (the AA, BB, AA, TTT, etc), then you could look at each word as a single character, so map AA->a, BB->b, TTT->t etc, now from your example the new "reduced" string is abatab. Find all substrings of abatab and check if each is a palindrome, if so then you can print out the original string by looking up the word in the map. An example is aba -> AABBAA.

The problem gets more interesting if your words are not all composed of the same letters. If you had AB BA. In this case AB and BA are not palindromes but the concatenation of them is ABBA.

fo_x86
  • 2,583
  • 1
  • 30
  • 41
0

SauceMaster's answer describes how to solve the palindrome problem.

I just want to answer this question.

I know how to find palindromes in a single string and if I merge these strings by removing the " " character, I can still find the palindromes...but if I do so, how do I reconstruct the original words?

Make a copy of the string first.

Community
  • 1
  • 1
Gilbert Le Blanc
  • 50,182
  • 6
  • 67
  • 111