Longest Common Prefix in an array of Strings in java

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
In this post, we are going to see longest common prefix in array of Strings.
So lets say you have string array as below:
String[] strArr={"java2blog","javaworld","javabean","javatemp"};
So Longest common prefix in above String array will be "java" as all above string starts with "java".
Lets take one more example:
String[] strArr={"sqlblog","sql2world","sqlquery","sqlproc"};
So Longest common prefix in above String array will be "sql" as all above string starts with "sql".

Algorithm: 

  • Find minimum length String.
  • Iterate over array of String and if we find any mismatch with minimum length String, we break the loop and that index will give us longest common prefix of this array of String,

Java Program to find Longest Common Prefix:

Create a main Class called LongestCommonPrefixMain.java.
package org.arpit.java2blog;

public class LongestCommonPrefixMain {

 public static void main(String[] args)
 {
  String[] strArr={"java2blog","javaworld","javabean","javatemp"};
  String longestPrefix=getLongestCommonPrefix(strArr);
  System.out.println("Longest Prefix : "+longestPrefix);
 }
 public static String getLongestCommonPrefix(String[] strArr) {
     if(strArr.length==0) return "";
  // Find minimum length String
     String minStr=getMinString(strArr);
  
     int minPrefixStrLength=minStr.length();
     for(int i=0;i<strArr.length;i++){
         int j;
         for( j=0;j<minPrefixStrLength;j++){
             if(minStr.charAt(j)!=strArr[i].charAt(j))
                 break;
         }
         if(j<minPrefixStrLength)
             minPrefixStrLength=j;
     }
     return minStr.substring(0,minPrefixStrLength);
 }
 public static String getMinString(String[] strArr)
 {
  String minStr=strArr[0];
   for(int i=1;i<strArr.length;i++){
          if(strArr[i].length()<minStr.length())
              minStr=strArr[i];
      }
   return minStr;
 }
}
When you run above program, you will get below output:
Longest Prefix : java

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012