Just to add more details: Overall time complexity will be O(nlogn) If hash maps are used for step (3), then searching becomes O(1). The time xomplexity then reduces to O(n).
On Aug 24, 10:15 am, bugaboo <bharath.sri...@gmail.com> wrote: > Hey group, > > Just wondering what the hullabaloo is since I see various dynamic > programming solutions. What do you think is wrong or non-elegant about > the following (quite intuitive) logic: > > 1) Do a DFS for node1 [O(n)] and store path in string str1 > 2) Do a DFS for node2 [O(n)] and store path in string str2 > 3) Scan the shorter string (say, str2 in this case) from right to > left. Search for each character in str1 [O(nlogn] > 4) Stop if you find a hit in step(3). The hit character represents the > LCA node -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.