CODEWITHSUNDEEP
c++algorithmsearchpalindrome
Eduard Rostomyan
Eduard Rostomyan

Reputation: 6546

Constructing palindrome from a list of words

Recently I was looking through some interview questions, and found some interesting one:

You are given a list of word. Find if two words can be joined to-gather to form a palindrome. eg Consider a list {bat, tab, cat} Then bat and tab can be joined to gather to form a palindrome. Expecting a O(nk) solution where n = number of works and k is length

There can be multiple pairs, just return true if found one.

Also, in the comments one of the approaches was this:

1) Add the first word to the trie ( A B)
2) Take the second word (D E E D B A) and reverse it (A B D E E D)
3) See how many letters in the reversed word you can match in the trie (the first 2)
4) Take the rest of the string (D E E D) see if it is a palindrome if it is you are done return true
5) add the second word to the trie (D E E D B A)
6) go back to step 2 with the next word
7) when out of words return false

But in my opinion this is not an O(nk) solution.

Can anyone suggest a solution?? Or explain why the algorithm described above is O(nk)??

Upvotes: 1

Views: 922

Answers (2)

Jennifer Wood
Jennifer Wood

Reputation: 80

There's a really interesting discussion of this in an article from Dr. Dobbs, way back in 2004. The full explanation is a little long, but the general idea is:

Suppose you start with Lion, where the pivot is left of the actual word. I can calculate the center of the string, which is position two. The pivot is at zero, so the string is too heavy on the right, but at the moment, Lion qualifies as a partial palindrome. The "dot" at the pivot point matches the dot at the pivot point, so there is at least one correct character, albeit the same character. You now wish to prepend words that end with noil, attempting to convert the string to noil.Lion. I use to mean any string of characters. If you're successful, then you need to locate words starting with so that they can be appended to the string.

Note that he defines a partial palindrome as:

A string is a partial palindrome if, working from the pivot point outwards, either the left or right end of the string is encountered before a mismatch occurs.

Upvotes: 0

luk32
luk32

Reputation: 16070

The algorithms is correct, or at least it gets quite close. There are minor technical issues. In step 4. one should save the proposition of a solution if it's better than the current one, and in step 7. return it, or say it was impossible to make a palindrome.

The main idea is to process words into cores and prefixes. If a core is a palindrome, then we need to match the prefix with other word. Trie serves as a "database" for processed strings, so with each new word, one can check all possible extensions. If words were kept separately one would need to compare prefixes of each word separately.

(Edit: I think there still is a small loophole, in case there are two words in a trie which starts the same, and the incoming one would make a palindrome with the shorter one, but not the longer, but I won't go into details. Handling it would complicate the algo but wouldn't affect complexity.)

It also is O(n*k). Adding and checking a prefix vs a trie takes number of steps proportional to the number of characters. So in this case this is bound by k. Just like tree operations are O(h) where h is the height of the tree. So in conclusion:

  1. k steps.

  2. takes k steps.

  3. also takes at most k steps.

  4. also takes less than k steps but we can bound it by k.

  5. also takes k steps.

Steps 2 to 5 are done n-1 times.

Of course each step has a different dominant operation, so it is hard to specify the exact constant, but all of them are bound by k so the complexity is O(c*(n-1)*k) which essentially is O(n*k).

Upvotes: 2

Related Questions