|
163. How do you find the longest palindrome in a given string ?
Microsoft Interview Questions and Answers
(Continued from previous question...)
163. How do you find the longest palindrome in a given string ?
Question:
How do you find the longest palindrome in a given string ?
maybe an answer:
create a new string R (R is the reverse of S)
now create a general suffix tree with these two strings S# and R$.
The longest path from the root to a node which has its children nodes $ and # is the longest palindrome.
maybe an answer2:
1. assume original string is S
2. reverse each word in the sentence and store it in string R
3. now compare each word in S, R and find longest matching word
this can be done in O(n)
step 2 can be done in O(n) time using some extra space.
Reverse the whole sentence, then split it and copy the words from last.
Ex :
Assume string is "I am aabaa"
reverse the string "aabaa ma I"
split it - "aabaa", "ma", "I"
now, copy this words (from last) to new string,
I ma aabaa
(Continued on next question...)
Other Interview Questions
| 