Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

Solution:

The requirement here is to find longest common prefix amongst an array of strings. 

There are many approaches to this problem but the one that I am going to discuss here uses Trie to store the array of strings and then scan the trie to get the longest common prefix.

To know more about Trie, you can visit here.

Algorithm:

1) Store each string from the array of strings in Trie.

2) Get the deepest Trie Node such that all the nodes from the root of the trie to that node has only one children.

	public class TrieNode{
	public bool isEndOfWord;
	public TrieNode[] children;
	public TrieNode(){
	isEndOfWord = false;
	children = new TrieNode[26];
	for(int i=0;i<26;i++){
	children[i] = null;
	}
	}
	}
	public class Solution {
	public TrieNode root;
	public void Insert(string str){
	TrieNode temp = root;
	int len = str.Length;
	for(int i=0;i<len;i++)
	{
	int index = str[i]-'a';
	if(temp.children[index] == null){
	temp.children[index] = new TrieNode();
	}
	temp = temp.children[index];
	}
	temp.isEndOfWord=true;
	}
	public string GetPrefix(){
	if(root == null){
	return "";
	}
	TrieNode temp = root;
	string prefix = "";
	bool loop = true;
	while(loop && !temp.isEndOfWord){
	TrieNode found = null;
	int index = 0;
	for(int i=0;i<26;i++){
	if(temp.children[i]!=null){
	if(found == null){
	found = temp.children[i];
	index = i;
	}
	else{
	loop = false;
	}
	}
	}
	if(loop){
	prefix = prefix + (Convert.ToChar(index+'a')).ToString();
	}
	temp = found;
	}
	return prefix;
	}
	public string LongestCommonPrefix(string[] strs) {
	root = new TrieNode();
	int len = strs.Length;
	if(len==0){
	return "";
	}
	for(int i=0;i<len;i++){
	Insert(strs[i]);
	}
	string prefix = GetPrefix();
	return prefix;
	}
	}

view raw LongestCommonPrefix.cs hosted with ❤ by GitHub

Space Complexity: O(n) where n is the number of unique characters in the array of string.

Time Complexity: O(n) for building the Trie (n is the number of unique characters in the array of string) and O(m) for finding the prefix (where m is the length of the prefix).