Find the longest common prefix?

Question

In two lines:

"Mary had a little lamb"
"Mary had a big lamb"

must return

"Mary had"

Answer 1

You do not need to use StringBuilder - just return the substring:

 public String greatestCommonPrefix(String a, String b) { int minLength = Math.min(a.length(), b.length()); for (int i = 0; i < minLength; i++) { if (a.charAt(i) != b.charAt(i)) { return a.substring(0, i); } } return a.substring(0, minLength); } 

Answer 2

 public class Test{ public static void main(String[] args){ String s1 = "Mary Had a Little Lamb"; String s2 = "Mary Had a Big Lamb"; int minStrLen = s1.length(); if ( minStrLen > s2.length()){ minStrLen = s2.length(); } StringBuilder output = new StringBuilder(); for(int i=0; i<minStrLen; i++){ if ( s1.charAt(i) == s2.charAt(i)){ output.append(s1.charAt(i)); }else{ break; } } System.out.println(output.toString()); } } 

This may not be the optimal solution, but it is easy to understand and program.

I borrowed this idea from the merge-merge- list merge method. If you read a little about the method of combining lists, you better understand the logic of my algorithm.

Answer 3

 String str1; String str2; // assuming str1.length > str2.length 

• a.startsWith (b) == true if not
• in the loop, remove the last char from str1 and repeat the verification of step 1.

Answer 4

This solution applies to an array with multiple rows. When you have 3 or 4 lines, it is better to use StringBuilder. For 2 lines, it is ok to use a substring. Code in C #:

  public string LongestCommonPrefix(string[] strs) { if(strs.Length == 0) return string.Empty; Array.Sort(strs); var first = strs[0]; var last = strs[strs.Length - 1]; var sb = new StringBuilder(); for(int i = 0; i< first.Length; i++) { if(first[i] != last[i]) { break; } sb.Append(first[i]); } return sb.ToString(); } 

Answer 5

Use binary search. Try comparing whole lines. If they are not equal, try comparing the first characters. If they are equal, try to split the strings ( substring(0, str.length()/2 ). Etc, etc.