Longest public prefix

Subject address: leetcode-cn.com/problems/lo…

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:

Input:"flower"."flow"."flight"] output:"fl"
Copy the code

Example 2:

Input:"dog"."racecar"."car"] output:""Explanation: The input does not have a common prefix.Copy the code

Description:

All inputs contain only lowercase letters A-z.

Solution one: horizontal comparison

To find a common prefix for multiple strings we don’t know, but we know at least to find a common prefix for two strings. So pair by pair, find the last common prefix until n-1 iteration completes the final common prefix, so like the first example of three strings, it takes 2 iterations

That is, we take one common prefix and the next one gets the common prefix and then we update the overlay and start the next iteration. So let’s start by specifying STRS [0] as the public prefix of the first generation. Here is the code that commits successfully for the first time:

public String longestCommonPrefix(String[] strs){
    int n = strs.length;
    if(strs.length == 0) return "";
    // The initial public prefix
    String common = strs[0];
    // There are n-1 iterations in pairs
    for(int i = 1; i < n; i++){
        // An iterative process
        int j = 0;
        char[] cur = common.toCharArray();
        char[] next = strs[i].toCharArray();
        // STRS array with two string boundaries
        if(next.length == 0) return "";
        while( j < cur.length && j < next.length ){
            // If the index is different, the index is the same as the last one
            if(cur[j] ! = next[j]){ common = common.substring(0,j);// Note that the interval is left closed and right open
                break;
            // No different but has been scanned, then the index is the same last one
            }else if(j == cur.length - 1 || j == next.length - 1){
                common = common.substring(0,j+1);
                break; } j++; }}return common;
}
Copy the code

But there is a problem with this code, and the question we need to think about is whether the operations inside the loop can be reduced, even though the time complexity doesn’t change. But reducing the number of operations in the loop body can also be improved exponentially. It is not a problem to observe how many times the code first iterates through a for loop, but to focus on the code during one iteration. Let’s take this code out:

while( j < cur.length && j < next.length ){
    // If the index is different, the index is the same as the last one
    if(cur[j] ! = next[j]){ common = common.substring(0,j);// Note that the interval is left closed and right open
        break;
    // No different but has been scanned, then the index is the same last one
    }else if(j == cur.length - 1 || i == next.length - 1){
        common = common.substring(0,i+1);
        break;
    }
    j++;
}
Copy the code

Let’s look at the body of the loop, because there’s a break in both if segments, so there’s three if segments that can only go one. Let’s see if the two if operations can be combined. Clever friend should be able to react quickly, is nothing more than ever more than lead to scanning is intercept [0, j) and [0, j + 1), then in fact as long as it doesn’t satisfy the two equal out of the loop so index is added after the last equal 1, and no judgment interception of [0, j). The code can reduce the part immediately

while( j < cur.length && j < next.length && cur[j] == next[j]){
    j++;
}
common = common.substring(0,j);// Note that the interval is left closed and right open
Copy the code

It also reduces the amount of work we do in the loop. If we have n cycles, then we have 2 or 3 cycles so we have 2 or 3n cycles, so we’re trying to minimize the number of cycles in the inner layer. In addition to the body of the loop, the while condition is also executed along with the loop because it’s short-circuited and it might execute one end or it might execute three things, so we can reduce it by one

int length = cur.length > next.length ? next.length : cur.length;
while( j < length && cur[j] == next[j]){
    j++;
}
common = common.substring(0,j);// Note that the interval is left closed and right open
Copy the code

It’s like we’re adding an operation to the outer layer but we’re removing an operation from the loop, and it’s not much of an optimization but it doesn’t change the way we think about the problem and the data structure and so on

public String longestCommonPrefix(String[] strs){
    int n = strs.length;
    if(strs.length == 0) return "";
    // The initial public prefix
    String common = strs[0];
    // There are n-1 iterations in pairs
    for(int i = 1; i < n; i++){
        // An iterative process
        int j = 0;
        char[] cur = common.toCharArray();
        char[] next = strs[i].toCharArray();
        // STRS array with two string boundaries
        if(next.length == 0) return "";
        int length = cur.length > next.length ? next.length : cur.length;
        while( j < length && cur[j] == next[j]){
            j++;
        }
        common = common.substring(0,j);// Note that the interval is left closed and right open
    }
    return common;
}
Copy the code

Solution two: longitudinal comparison

In fact, the solution THAT I came up with at the beginning was to scan multiple strings at the same time and each string has the same number of characters and then scan all the way back until I get the first difference and then stop.

But there was just an intuitive idea that one line would be the same and then I couldn’t handle it and I thought it would be easier to write horizontally

int i = 0;
while( i < min(length) && str1[i] == str2[i]==..... ) { i++; }Copy the code

In fact, take a string traversal, in a traversal of the number of other strings are compared

public String longestCommonPrefix(String[] strs) {
    // return ""
    if (strs.length == 0) return "";
    // Take the array to reduce charAt in the loop body
    char[] p = str[0].toCharArray();
    int n = p.length;
    for (int i = 0; i < n; i++) {
        char c = p[i];
        // Check in order until the difference occurs, intercept return
        for (int j = 1; j < strs.length; j++) {
            if(i == strs[j].length() || strs[j].charAt(i) ! = c) {return strs[0].substring(0, i); }}}return strs[0];
}
Copy the code

Solution 3: Variants (Solution 1)

We can also check whether the prefix contains another string at the starting index by using a.startswith (b), or by using a.indexof (b) == 0. If you don’t have one, subtract one until you find the common prefix and start the next iteration. It’s the same thing as finding the common prefix in a different way

public String longestCommonPrefix(String[] strs) {
    // return ""
    if (strs.length == 0) return "";
    String common = strs[0];
    for (String str : strs) {
        // If common has been reduced to "", there is no public prefix
        if (common == "") return common;
        // If common does not match in the current STR, reduce the length of the string common and try again
        while(! str.startsWith(common)) { common = common.substring(0,common.length() - 1); }}return common;
}
Copy the code

conclusion

In general, the time complexity is quite high, plus substring and other methods over n to the third power. It’s almost the same as the last problem and both of these problems are a process of experiencing an iteration and you can also translate it into a recursive form. Once the string series in this LeetCode primer algorithm collection is complete, open the next chapter linked list.