×

String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding

Miscellaneous

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 [Last updated : March 20, 2023]

Problem Description

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 of Longest Common Prefix

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 for Longest Common Prefix

#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!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.