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

If there is no common prefix, return an empty string "".

Input: strs = ["flower","flow","flight"]
Output: "fl"

public static String longestCommonPrefix(String[] strs) {

        String common="";

        for(int i=0; i<strs.length-1; i  ){
         
          if(strs[i].charAt(i)==strs[i 1].charAt(i)){
              common =strs[i].charAt(i);
          } else
              return common;  
        }
        return common;
    }

My code does work for this case but when i try for just two for example if i enter

["flower","flow"];

I just get f common. I cannot see which part I am wrong. Can someone help out?

CodePudding user response：

Another variation, going char by char instead of using StartsWith():

  public static String longestCommonPrefix(String[] strs) {
    int index = 0;
    String prefix = "";
    String current = "";
    boolean allSame = true;
    
    while (allSame && index < strs[0].length()) {
      current = strs[0].substring(index, index 1);
      for(int i=1; i<strs.length && allSame; i  ) {
        allSame = (index < strs[i].length()) && 
                   strs[i].substring(index, index 1).equals(current);
      }
      if (allSame) {
        index  ;
        prefix = prefix   current;
      }
    }
    
    return prefix;
  }

CodePudding user response：

Notice how the following code makes sure to check all of the strings and not just consecutive ones:

public static String findCommon(String[] strs) {
    String common = ""; //common prefix (the result)
    String checkedPrefix;
    int index = 0;
    boolean mostCommonPrefix = false; //Flag for when the most common prefix was found

    while (index < strs[0].length() && !mostCommonPrefix) {
        //The checked prefix is our currently most common prefix
        //with 1 more character added from the first string in the array
        checkedPrefix = common   strs[0].charAt(index  );
        for (int i = 1; i < strs.length; i  ) {
            //If at least one of our strings doesn't start with the checked prefix
            //then common is our most common prefix
            if (!strs[i].startsWith(checkedPrefix)) {
                mostCommonPrefix = true;
                break;
            }
        }
        //Otherwise we set common to checked prefix (cause all of our strings start with it)
        if (!mostCommonPrefix)
            common = checkedPrefix;
    }

    return common;
}

CodePudding user response：

public static String commonPrefix(String[] arr) {
    String prefix = "";   // in case arr is empty
    if (arr.length > 0) {
        prefix = arr[0];
    }

    for (int i = 1; i < arr.length && prefix.length() > 0;   i) {
        for (int j = 0; j < prefix.length() && j < arr[i].length();   j) {
            if (arr[i].charAt(j) != prefix.charAt(j)) {
                prefix = prefix.substring(0, j);
            }
        }
    }
    return prefix;
}

This starts with the assumption the first element in the array is the common prefix. It then loops through the rest of the array. It uses a nested for loop to compare the prefix against the indexed element from the array. It goes character-by-character until a difference is found. If / When a difference is found, it shortens the prefix.

I went character-by-character instead of using one of the startsWith because, if startsWith returned false, I would need additional code to find a shorter length for prefix.

The length of prefix can never increase. So, the continuing expression in the outer for loop contains && prefix.length() > 0. If the length of prefix has reached zero, it has been determined there is no common prefix, so the loop need not continue.

I deliberately left a bug in this code for the reader to find and correct.