@Lucifer:
Ya,got it now..thanks a lot! :)
On Thu, Dec 29, 2011 at 7:43 AM, Lucifer sourabhd2...@gmail.com wrote:
@rajat..
First of all.. sorry for the late reply :)
Below i have explained the dp approach by taking.. Once u trace it u
will be able to understand the code..
Lets denote the
given question is :-
Given a string of length N, find whether there exits an even length
palindrome substring.
question is unclear, you want a palindrome whose substring of even length
is present in the given string of length N, right ? where the palindrome is
itself formed from the given
@shady : lets go with this one:-
given string = *abcdrdcba
abcd != dcba - not a palindrome
**abcd != dcba - **not a palindrome *
*
*no even length palindrome found for the given string.
given string = ab*cddc*abr
even lenght palindrome found = cddc
if another even length palindrome found
@sumit
How do u guarantee O(N) in..
T(n) = T(n/2) + O(n)..
I don't think just searching from the middle would cover all the
cases...
Say u have array of size 20 partitioned in 2 subarrays of sizes 10 and
10..
Now from left subarray u have a plaindrome of some recorded length..
Similarly from
I found something similar algorithm . one hich DFS and BFS
algorithm :- one named Trémaux's algorithm uses DFS
and for finding the shortest path it used Shortest path algorithm .
Follow the link and find the these algorithms here ..
http://en.wikipedia.org/wiki/Maze_solving_algorithm
--
You
@Lucifer : in your first approach ...
i guess outer loop should start from 1 and inner loop should move n to 1..
in the given algo both outer and inner loop move from N to 1.
will your algo work for this case??
string = abccba
i.e when given string itself is longest even length palindrome.
@Editing mistake for the comment in the innermost 'If' loop..
We need *not check for the case where the reverse substring is placed
before the orig substring as its symmetric..
On Dec 29, 7:12 pm, Lucifer sourabhd2...@gmail.com wrote:
@shady
I am re-posting the code.. Somehow the format is
@atul
The loop runs are correct..
Yes, it works fine for abccba giving out 6 as the max length of even
palindrome which is nothing but the entire string..
On Dec 29, 4:16 pm, atul anand atul.87fri...@gmail.com wrote:
@Lucifer : in your first approach ...
i guess outer loop should start from
@shady...
The first approach with a slight modification will solve the above
mentioned problem...
I have modified the previous to show the same..
The innermost 'If' statement needs to be modified to ensure that the
found substring which is present in both the originalStr and
reverseStr doesn't
oh, i didn't read all the posts, anyway i have understood lucifier's O(n^2)
time solution.
and ya what's the solution for this question?
Given a string of length N, find whether there exits an even length
reverse substring of a substring.
On Thu, Dec 29, 2011 at 2:23 PM, atul anand
@shady... The first approach with a slight modification will solve the
above mentioned problem... I have modified the previous to show the
same..
The innermost 'If' statement needs to be modified to ensure that
the found substring which is present in both the originalStr
and reverseStr doesn't
IT will grt help for me... if u all tell me..
mapstring,int m;
m[topcoder]=2
My question is this:
Is 2 is an key value??or index value of hash table...??...
kindly explain how actual mapping is done... in hash table...plz...
PRAVEEN RAJ
DELHI COLLEGE OF ENGINEERING
On Tue, Dec 27,
@RAJ
Can u explain ur dp approach... For ex- what is i and j in LP(i,j) ?
On 29 Dec, 19:14, Lucifer sourabhd2...@gmail.com wrote:
@Editing mistake for the comment in the innermost 'If' loop..
We need *not check for the case where the reverse substring is placed
before the orig substring as
@shady...
The first approach with a slight modification will solve the above
mentioned problem...
I have modified the previous to show the same..
The innermost 'If' statement needs to be modified to ensure that the
found substring which is present in both the originalStr and
reverseStr doesn't
steps:
1) use hash mapping to keep track of frequency of each and every element.
2)Then iterate hash table and store in 2D array with 1st column(element
value) and 2nd column(frequency of element value).
3)sort the row according to second column(i.e frequency).
4)Then Print the
@shady
I am re-posting the code.. Somehow the format is getting messed up...
while ( pRev 0)
{
for ( pStrt = N; pStrt =1 ; --i)
{
if ( OrigStr[pStrt] == OrigStr[pRev] )
{
X[pStrt] = 1 + X[pStrt - 1];
if ( (X[pStrt] % 2 == 0)
(currMax X[pStrt])
same question as above with one more task is given
4) FindAnyElement()
which will return any element present in that structure with O(1).
for given all 4 task
Please suggest which Data Structure is better now...?
Best Regards,
Pankaj Agarwal
--
You received this message because you are
Procedure:
1.if out of boundary return 0;
2.If reach final point return 1.
3.if(next point has no obstacle then go for it.. recursively)
PRAVEEN RAJ
DELHI COLLEGE OF ENGINEERING
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
Input : You have been given a sequence of integers.
Now without actually constructing BST from the given sequence of
integers (assuming the sequence is pre-order) determine if each node
of BST has single child (either left or right but not both).
Output : YES if given integer sequence
19 matches
Mail list logo
