Longest Common Prefix Editorial

Practice Problem Link: Longest Common Prefix | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement 

Given a list of strings A, find the longest common prefix among all the strings.

Naive Approach

A simple solution is to traverse the list and calculate the longest common prefix of each string with the longest common prefix found so far.

Analysis

• Time Complexity: O(n * (Max String Size))
• Auxiliary Space Complexity: O(1)

Implementation

C++

string longestCommonPrefix(vector<string> str) {
   string lcp = str[0];
   for (int i = 1; i < str.size(); i++) {
       string commonPrefix;
       for (int j = 0; j < min (lcp.size(), str[i].size()); j++) {
           if (lcp[j] == str[i][j]) {
               commonPrefix += lcp[j];
           } else {
               break;
           }
       }
       lcp = commonPrefix;
   }
   return lcp;
}

Java

class Solution {
   String longestCommonPrefix(String[] str) {
       String lcp = str[0];
       for (int i = 1; i < str.length; i++) {
           String commonPrefix  = "";
           for (int j = 0; j < Math.min(lcp.length(), str[i].length()); j++) {
               if (lcp.charAt(j) == str[i].charAt(j)) {
                   commonPrefix += lcp.charAt(j);
               } else {
                   break;
               }
           }
           lcp = commonPrefix;
       }
       return lcp;
   }
}

Optimal Approach

The optimal and better approach for this problem is to sort the given strings and compare the first and last string to find the longest common prefix. The reason behind checking the first and last strings only is that all the strings in-between must have the same prefix as the strings are sorted lexicographically. 

Analysis

• Time Complexity: O(n * logn + (Max String Size))
• Auxiliary Space Complexity: O(1)

Implementation

C++

string longestCommonPrefix(vector<string> str) {
   sort (str.begin(), str.end());
   int n = str.size() - 1;
   string lcp;
   for (int i = 0; i < min (str[0].size(), str[n].size()); i++) {
       if (str[0][i] == str[n][i]) {
           lcp += str[0][i];
       } else {
           break;
       }
   }
   return lcp;
}

Java

class Solution {
   String longestCommonPrefix(String[] str) {
       Arrays.sort (str);
       int n = str.length - 1;
       String lcp = "";
       for (int i = 0; i < Math.min (str[0].length(), str[n].length()); i++) {
           if (str[0].charAt(i) == str[n].charAt(i)) {
               lcp += str[0].charAt(i);
           } else {
               break;
           }
       }
       return lcp;
   }
}