Longest Common Prefix - using Trie

Sept. 7, 2016

Work on C# practice:
http://www.geeksforgeeks.org/longest-common-prefix-set-5-using-trie/

One of longest common prefix series:
1. http://www.geeksforgeeks.org/longest-common-prefix-set-1-word-by-word-matching/
2. http://www.geeksforgeeks.org/longest-common-prefix-set-2-character-by-character-matching/
3. http://www.geeksforgeeks.org/longest-common-prefix-set-3-divide-and-conquer/
4. http://www.geeksforgeeks.org/longest-common-prefix-set-4-binary-search/
5. http://www.geeksforgeeks.org/longest-common-prefix-set-5-using-trie/

Will work on coding very soon.

C# practice:
https://gist.github.com/jianminchen/d65887908a16e1c12d708a2912c4c081

Add time complexity and auxiliary space detail:
Time Complexity : Inserting all the words in the trie takes O(MN) time and performing a walk on the trie takes O(M) time, where-

N = Number of strings

M = Length of the largest string string

Auxiliary Space: To store all the strings we need to allocate O(26MN) ~ O(MN) space for the Trie.

From the website:

http://www.geeksforgeeks.org/longest-common-prefix-set-5-using-trie/

Editorial Notes:

1. This is the first C# implementation of Trie Julia wrote.

2. How does she get here?

HackerRank code sprint #6 has an algorithm related to suffix array ->

continue to work on suffix array ->

Longest common prefix ->

string search speed up ->

found a 5 solution series on geeksforgeeks ->

work on 5th solution, Trie, LCP

3. Prior experience worked on suffix array:

http://juliachencoding.blogspot.ca/2016/04/april-11-2016-plan-to-work-on-lcp-array.html
http://juliachencoding.blogspot.ca/2016/04/april-11-2016-plan-to-work-on-lcp-array.html

Try to solve the advanced problem again after 5 month (April, 2016) using suffix array, LCP, two pointer technique:
https://www.hackerrank.com/challenges/string-function-calculation