caffeine_coder
BAN USERCall Rev for the entire string and then call Rev for each word.
- caffeine_coder November 10, 2009The formatting there incorrect. The 4th node links to the 2nd node.
- caffeine_coder November 06, 2009I think the question is about deleting a LL like this,
1->2->3->4
^ |
|_____|
In which case, the code above will end up freeing the 2nd node twice.
You'll have to,
1. Find the loop
2. Find the loop node
3. Break the loop
4. Delete as usual
All that can be done in O(n)
?
- caffeine_coder November 06, 2009To find LCA for nodes A and B:
O((logn)^2):
1. Find in A in left subtree, B in right subtree
2. If both not found, find in A in right subtree, B in left subtree
3. If both found, current node is the common LCA
4. If one found and not the other, make a recursive to call to that branch of the tree and start from 1.
O(nlogn) with O(n) space:
1. Traverse the tree until node A is found, store the path in an array a1.
2. Traverse the tree until node B is found, store the path in an array a2.
3. Compare a1 and a2, the last common element is the LCA.
But there are better, more complicated ways of doing this in constant time using RMQ.
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Lowest%20Common%20Ancestor%20%28LCA%29
In a string of length n1 if the length of the longest palindrome is n2 (n2 <= n1), then to convert the entire string to a palindrome it would take (n1 - n2) characters. So, the problem boils down to just finding the longest palindrome in the string (which has been discussed in before on this site.)
- caffeine_coder November 21, 20091. PLATE
n1 = 5
n2 = 1
chars needed = 4
Result: PETLALTEP
2. MADA
n1 = 4
n2 = 3
chars needed = 1
Result: MADAM