Monday, May 15, 2017

Longest Common Prefix

Problem statement

Write a function to find the longest common prefix string among an array of strings

Link to GitHub : code




Example
Input  : {"tommorow", "tommy", "tomandGerry", "tod"}
Output : "to"

Input  : {"prathap", "pradeep", "prathish"}
Output : "pra"

Solution

  • Take the first string in the array of strings at let us assume that it is a prefix
  • Take the second string and compare it with prev string to find the first occurrence .
         strs[i].indexOf(pre)!=0
          Note: If it finds the occurrence then it would return 0 else -1
  • Iterate through the array of strings till we find the longest common prefix
public static String get(String [] strs)
 {
  //Check if the string array is null or the length is zero
  if (strs.length==0 || strs==null ) return "";
  
  //Get the first string in the array of strings
  String pre=strs[0];
  int i=1;
  //iterate till the end of the array
  while(i <strs.length)
  {
   //We are taking the second string and comparing if 
                        //index of previous returns 0 
   //If it returns zero we know that its common prefix
   while(strs[i].indexOf(pre)!=0)
    pre=pre.substring(0, pre.length()-1);
   i++;
  }
  return pre;
 }

Iteration


No comments:

Post a Comment