Last active
September 9, 2016 20:31
-
-
Save jianminchen/d65887908a16e1c12d708a2912c4c081 to your computer and use it in GitHub Desktop.
Longest common prefix - using Trie - source code reference: http://www.geeksforgeeks.org/longest-common-prefix-set-5-using-trie/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace LongestCommonPrefix_Trie | |
{ | |
/* | |
* First writing: | |
* source code reference: | |
* http://www.geeksforgeeks.org/longest-common-prefix-set-5-using-trie/ | |
* | |
* Write using C#: | |
* highlights of writing: | |
* 1. First, write insert function | |
* line 59 - need to add statement for next iteration - | |
* 2. walkTrie - output to char, type conversion is missing - (char) | |
* 3. countChildren function index ref int argument - confusion | |
* actually the function is used to iterate the LCP string | |
*/ | |
//https://msdn.microsoft.com/en-us/library/ms229017(v=vs.110).aspx | |
// figure out when to use struct or class in C# | |
class TrieNode | |
{ | |
const int ALPHABET_SZIE = 26; | |
TrieNode[] children = new TrieNode[ALPHABET_SZIE]; | |
bool isLeaf; | |
public TrieNode getNode() | |
{ | |
TrieNode node = new TrieNode(); | |
node.isLeaf = false; | |
for (int i = 0; i < ALPHABET_SZIE; i++) | |
node.children[i] = null; | |
return node; | |
} | |
/* | |
* Test case: | |
* add "geeksforgeeks" to the trie. | |
*/ | |
public void insert(TrieNode root, string key) | |
{ | |
int length = key.Length; | |
TrieNode pCrawl = root; | |
for (int level = 0; level < length; level++) | |
{ | |
int index = charToIndex(key[level]); | |
if (pCrawl.children[index] == null) | |
pCrawl.children[index] = getNode(); | |
pCrawl = pCrawl.children[index]; // bug001 -forget to add | |
} | |
// mark last node as leaf | |
pCrawl.isLeaf = true; | |
} | |
/* | |
* Counts and returns the number of children of the current node | |
*/ | |
public int countChildren(TrieNode node, ref int index) | |
{ | |
int count = 0; | |
for (int i = 0; i < ALPHABET_SZIE; i++) | |
{ | |
if (node.children[i] != null) | |
{ | |
count++; | |
index = i; | |
} | |
} | |
return count; | |
} | |
/* | |
* Perfrom a walk on the trie and return the longest common prefix string | |
* use of unsigned local variable 'index' | |
*/ | |
public string walkTrie(TrieNode root) | |
{ | |
TrieNode pCrawl = root; | |
int index = 0 ; | |
StringBuilder prefix = new StringBuilder(); | |
while (countChildren(pCrawl, ref index) == 1 && | |
pCrawl.isLeaf == false) | |
{ | |
pCrawl = pCrawl.children[index]; | |
prefix.Append((char)('a'+index)); | |
} | |
return prefix.ToString(); | |
} | |
// A Function to construct trie | |
void constructTrie(string[] arr, int n, TrieNode root) | |
{ | |
for (int i = 0; i < n; i++) | |
insert (root, arr[i]); | |
return; | |
} | |
// A Function that returns the longest common prefix | |
// from the array of strings | |
public string commonPrefix(string[] arr, int n) | |
{ | |
TrieNode root = getNode(); | |
constructTrie(arr, n, root); | |
// Perform a walk on the trie | |
return walkTrie(root); | |
} | |
private int charToIndex(char c) | |
{ | |
return c - 'a'; | |
} | |
// Driver program to test above function | |
public static void Main(string[] args) | |
{ | |
string[] arr = {"geeksforgeeks", "geeks", | |
"geek", "geezer"}; | |
int n = arr.Length; | |
TrieNode test = new TrieNode(); | |
string ans = test.commonPrefix(arr, n); | |
if (ans.Length > 0) | |
Console.WriteLine("The longest common prefix is " | |
+ ans.ToString()); | |
else | |
Console.WriteLine("There is no common prefix"); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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(26_M_N) ~ O(MN) space for the Trie.
From the website:
http://www.geeksforgeeks.org/longest-common-prefix-set-5-using-trie/