Find Longest Common Prefix Using Word by Word Matching in Java

In this article, we will explore how to find the longest common prefix among a given set of strings using two different approaches in Java. We will first discuss an approach that compares all strings directly to find the longest prefix and then move to a word-by-word matching approach. 

Problem Statement

We are given a set of strings and we have to find the common prefix among all of them. A prefix is a substring for a string that contains the zero index and could be of any length from 1 to a complete string.

Input 1

string arr[] = {"abcdefgh", "abcdefij", "abcdzy", "abcdabacd"};

Output 1

abcd

Explanation

From all the given strings, we have the first four characters the same and the remaining characters are not the same for all of them.

Input 2

string arr[] = {{"abcdefgh", "bcdefij", "acdzy", "abcdabacd"};}

Output 2

""

Explanation

In the given string, none of them shares the same prefix

Different Approaches 

Below are the different approaches to finding the longest common prefix using word-by-word matching

• Comparing All the Strings
• Word By Word Matching

Comparing All the Strings

In this approach, we will traverse all the strings one by one compare them with the first string, and store the answer in another string.

Following are the steps to find the longest common prefix using word-by-word matching

• Initialize the prefix variable and set the first string arr[0] as the initial prefix.
  
• Use a for loop to traverse the array and compare the current string with the prefix.
  
• Compare strings using a while loop and inside the helper method commonPre, use a while loop to compare characters at the same position in both strings until a mismatch is found or the loop finishes.
• Use an if condition to check for character mismatch, if the characters don't match break the loop and if they do match, append the character to the prefix.
  
• Update the prefix after comparing it with each string, and update the prefix with the common part.
• Once the loop completes, return the final longest common prefix.

Example

public class Solution{
   // creating a function to find the longest common prefix of two given strings     
   static String commonPre(String str1, String str2){
      String ans = "";
      int len1 = str1.length(); // length of the string 1
      int len2 = str2.length(); // length of the string 2
      // comparing both teh strings until they are same 
      int i = 0; // pointer to traverse over both the string       
      while(i < len1 && i < len2){
         if(str1.charAt(i) != str2.charAt(i)){
            break;
         } else{
            // add the current character to the answer string 
            ans += str1.charAt(i);
         }
         i++;
      }
      return ans; // return the answer 
   } 
   // helper function that will return the final answer 
   static String helper(String arr[], int len){
      String pre = arr[0]; // initializing the prefix variable         
      // comparing the zeoth string with all the string 
      for (int i = 1; i < len; i++){
         pre = commonPre(pre, arr[i]);
      }
      return pre; // return the final answer 
   } 
   public static void main(String[] args) {        
      // given array 
      String arr[] = {"abcdefgh", "abcdefij", "abcdzy", "abcdabacd"};
      int len = arr.length; // getting length of the given array 
      String ans = helper(arr, len); // calling to the function  
      if (ans.length() > 0){
          // answer string is not empty 
          System.out.printf("The longest common prefix among the given strings is: %s", ans);
      } else{
         // answer string is empty 
         System.out.printf("There is no common prefix among the given strings");
      }
   }
}

Output

The longest common prefix among the given strings is: abcd

Time and Space Complexity

The time complexity of the above code is O(N*M), where N is the number of strings and M is the length of the strings.

The space complexity of the above code is O(M), as we have used a string to store the common prefix.

Word By Word Matching

In this approach, we are going to traverse over the first string and will use the for loop to traverse over the array and check for the current character of all the strings if is the same as of the first string or not.

• Create a helper function helper to find the longest common prefix.
  
• Start by looping through using for loop the characters of the first string.
  
• For each character, check if all other strings have the same character at the current index.
  
• If any string is shorter or has a different character, break the loop.
  
• Add matching characters to the result string and continue checking until a mismatch is found.
  
• In the main method, pass the array of strings to the helper function and print the longest common prefix if it's not empty.

Example

public class Solution{
   // helper function that will return the final answer 
   static String helper(String arr[], int len){
      String ans = ""; // string to store the answer         
      //traversging over the first string 
      for (int i = 0; i < arr[0].length(); i++) {
         boolean flag = true; // boolean variable to keep track             
         // compare all the string with the first string current word
         for(int j = 1; j < len; j++){
            if(arr[j].length() == i){
               // current string is smallest
               // so, break the loop 
               flag = false; 
               break;
            }
            else if(arr[j].charAt(i) != arr[0].charAt(i)){
               // current string's current character is not same 
               flag = false; 
               break;
            } else{
               // the current character is same for both the strings 
               continue;
            }
         }           
         if (flag) {
            ans += arr[0].charAt(i);
         } else {
            break;
         }
      }
      return ans; // return the answer
   } 
   public static void main(String[] args) {      
      // given array 
      String arr[] = {"abcdefgh", "abcdefij", "abcdzy", "abcdabacd"};
      int len = arr.length; // getting length of the given array 
      String ans = helper(arr, len); // calling to the function  
      if (ans.length() > 0){
         // answer string is not empty 
         System.out.printf("The longest common prefix among the given strings is: %s", ans);
      } else{
            // answer string is empty 
            System.out.printf("There is no common prefix among the given strings");
      }
   }
}

Output

The longest common prefix among the given strings is: abcd

Time and Space Complexity

The time complexity of the above code is O(N*M), where N is the number of strings and M is the length of the strings.

The space complexity of the above code is O(M), as we have used a string to store the common prefix.

Conclusion

In the above code, we have implemented a Java program to find the common prefix of the given string. We have implemented two approaches one is the direct traversal approach by comparing all the strings and another is the word-by-word match approach. The time complexity of both strings is O(N*M).