Home » Interview coding problems/challenges

Longest Common Prefix

In this article, we are going to see how to find longest common prefix from a set of strings? This problem can be featured in any interview coding round.
Submitted by Radib Kar, on January 09, 2019

Problem statement:

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 "".

Solution:

Input Example:

    Example 1:
    Let the set of strings to be {"flower", "fly", "flow"}
    The longest common prefix is "fl"

    Example 2:
    Let the set of strings to be {"dog", "donkey", "door", "cat"}
    The longest common prefix is "", i.e., empty string. 
    Since there is no common prefix at all. 

Longest common prefix

Longest common prefix simply means the longest prefix (prefix is a substring also, but not vice-versa) all the member strings consist of.

Algorithm to find longest common prefix of a set of strings

Solving particularly for two string, the problem is not that difficult what it is for a set of strings. But we can simply break the problem into sub-problems where we can solve for only two strings and simply pass the output for further string processing 's. In a simple word, the whole thing can be formulated to be:

    LongestCommonPrefix(string1, string2, ..., string n)
=   LongestCommonPrefix(LongestCommonPrefix(string1,string2),string3,...,string n)
=   LongestCommonPrefix(newstring1,string3,string4,...,string n)
=   ...
=   LongestCommonPrefix(newstring n-1, string n)
=   new string n = final result

So this simply converts the problem for a set of 
strings to a problem of two strings only

Finding longest common prefix for two strings (string x, string y)

  1. Check for base case
  2. IF anyone is empty string
        return empty string;
    
  3. Declare result as an empty string;
  4.     IF string x is smaller than y
    	    //check for common prefix part on basis of x
    		    FOR( i=0;i<length of string x; i++)
    		    IF(x[i]==y[i])
    		    result+=x[i]; //append the common character
    			    ELSE//no common character at this point
    			    Returnresult
    		    END FOR
    	
    	    ELSE//if string y is smaller than x
    	    //check for common prefix part on basis of y		
    		    FOR (i=0;i<length of y; i++)
    		    IF(y[i]==x[i])
    		    result+=y[i];//append the common character
    		    ELSE//no common character at this point
    		     return result;
    		    END FOR
    	    END IF-ELSE
    
  5. result consist of longest common prefix for these two strings

Explanation with example

    Let's consider the first example
    The set of strings: {"flower", "fly", "flow"}
    LongestCommonPrefix("flower", "fly", "flow")
=   LongestCommonPrefix(LongestCommonPrefix ("flower","fly"),"flow")
=   LongestCommonPrefix("fl", "flow")
=   "fl"

    Let's consider the second example
    the set of strings to be {"dog", "donkey", "door", "cat"}
    LongestCommonPrefix("dog", "donkey", "door", "cat")
=   LongestCommonPrefix(LongestCommonPrefix ("dog", "donkey"),"door", "cat")
=   LongestCommonPrefix("do","door", "cat")
=   LongestCommonPrefix (LongestCommonPrefix("do", "door") , "cat")
=   LongestCommonPrefix("do", "cat")
=   "" //empty string

C++ implementation

#include <bits/stdc++.h>
using namespace std;

string findPrefix(string x,string y){
	//base case checking
	if(x=="" || y=="")
		return "";
	
	string result="";

	//if string x is smaller than y
	if(x.length()<y.length()){
		//check up for common prefix part
		for(int i=0;i<x.length();i++){
			if(x[i]==y[i])
				result+=x[i];
		}
	}
	else{
		//if string y is smaller than x
		for(int i=0;i<y.length();i++){
			//check up for common prefix part 
			if(y[i]==x[i])
				result+=y[i];
			else
				return result;
		}
	}
	return result;
}

string longestCommonPrefix(vector<string>& strs) {
	//base cases
	if(strs.size()==0)
		return "";
	//if only one string exists
	if(strs.size()==1)
		return strs[0];
	string prefix=strs[0];
	//follow the associative property for checking 
	//take two strings each time & pass output prefix 
	//as one string for further processings
	for(int i=1;i<strs.size();i++){
		prefix=findPrefix(prefix,strs[i]);
		if(prefix=="")
			return prefix;
	}
	return prefix;
}

int main(){
	int n;
	cout<<"enter no of strings you want to add\n";
	cin>>n;
	
	string s;
	vector<string> v;
	cout<<"enter "<<n<<" strings\n";
	
	//collect input
	while(n--){
		cin>>s;
		v.push_back(s);
	}
	//print longest common prefix
	if(longestCommonPrefix(v)=="")
		cout<<"no common prefix between the strings\n";
	else
		cout<<"longest common prefix: "<<longestCommonPrefix(v)<<endl;

	return 0;
}

Output

First run:
enter no of strings you want to add
3
enter 3 strings
flower
fly
flow
longest common prefix: fl

Second run:
enter no of strings you want to add
4
enter 4 strings
dog
donkey
door
cat
no common prefix between the strings




Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.



Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.