Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Last active September 9, 2016 20:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/d65887908a16e1c12d708a2912c4c081 to your computer and use it in GitHub Desktop.
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/
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");
}
}
}
@jianminchen
Copy link
Author

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/

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment