This is the 16th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Today’s topic

Write a function to find the longest public prefix in an array of strings.

Returns the empty string “” if no public prefix exists.

Example 1:

STRS = [“flower”,”flow”,”flight”]

Example 2:

Input: STRS = [“dog”,”racecar”,”car”] Output: “” Explanation: The input does not have a common prefix.

Tip:

1 <= strs.length <= 200 0 <= STRS [I]. Length <= 200 STRS [I] consists of lowercase letters only

Train of thought

The common longest prefix feature: the prefix must exist in every string.

Compare the first string with other strings one by one to get the prefix length. And the smallest of all the lengths is the solution

Points that can be optimized:

  1. The common prefix cannot exceed the length of any string. Instead of comparing the entire string each time, just compare the current prefix length
  2. If there is no common prefix, there is no need to traverse the rest of the string

implementation

public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) {
        return "";
    }
    // The last position of the longest prefix
    int end = strs[0].length() - 1;
    for (int i = 1; i < strs.length; i++) {
        // Optimization 1: Instead of comparing the entire string, just compare the prefix length
        int j = 0;
        for (; j <= end && j < strs[i].length(); j++) {
            if (strs[0].charAt(j) ! = strs[i].charAt(j)) {// If the first character is not equal, no comparison is required
                if(j == 0) {return "";
                }
                break;
            }
        }
        end = Math.min(end, j - 1);
    }
    return strs[0].substring(0, end + 1);
}
Copy the code

Execution time: 1 ms, beating 70.59% of users in all Java commits

Memory consumption: 36.3 MB, beating 89.59% of all Java commits

Method 2

The second solution is actually the same idea as the first, but you can use the String API method

The startWith() method, which makes code implementation more elegant

 public String longestCommonPrefix(String[] strs) {
     if (strs.length == 0) {
         return "";
     }
     // Longest prefix
     String commonPrefix = strs[0];
     for (int i = 1; i < strs.length; i++) {
         while(! strs[i].startsWith(commonPrefix)) {if (commonPrefix.length() == 0) {
                 return "";
             }
             commonPrefix = commonPrefix.substring(0, commonPrefix.length() - 1); }}return commonPrefix;
 }
Copy the code

Execution time: 0 ms, beating 100.00% of users in all Java commits

Memory consumption: 36.5 MB, beating 44.26% of all Java commits

summary

The questions in these two days are relatively simple, but it is still difficult to write correctly at one time. You need to pay more attention to the common API writing methods

Such as:

  • Loop mode of map and entry writing
  • Substring (start, end)** [start, end)**
  • Strings and lists get string lengths using the method ss.length(), and arrays using the variable array.length
  • Interconversion between numbers and strings, string.valueof (int), integer.parsein (String) This method is not frequently unboxed
  • And do the problem have attention to the question, this problem I thought was to find the longest common substring

The more you learn today, the less you beg tomorrow