This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

Longest public prefix

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”] Output: “fl” Example 2:

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

Second, train of thought analysis

Longitudinal contrast method

• The simplest and most crude method is to compare. I don’t know what you think, lovely readers, but the first idea here is to compare the position of each string. Otherwise, the next step ends. Just plain and simple.

• We will line up the characters to be compared and compare the contents of each character in the index according to the same index. If they are the same, they will be added to our prefix. Otherwise end. In the figure, when we index to 2, we find that the flight I is different from the first two, so the longest prefix is our 0~1 partfl 。

AC code

public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) {
        return "";
    }
    int minLength = strs[0].length();
    String firstStr = strs[0];
    for (int i = 1; i < strs.length; i++) {
        minLength = Math.min(minLength, strs[i].length());
        if (minLength == 0) {
            return ""; }}for (int i = 0; i < minLength; i++) {
        for (int j = 1; j < strs.length; j++) {
            if(firstStr.charAt(i) ! = strs[j].charAt(i)) {return firstStr.substring(0, i); }}}return firstStr.substring(0, minLength);
}
Copy the code

• The end result is objective. Although the code looks cumbersome, it’s not too difficult to understand with my illustration above. We need variables to store indexes for easy control. We also need a variable for each string comparison at a specific index position

Dynamic programming method

• Comparing the specific positions of each string above is easy to understand, but the code implementation is really a bit convoluted. From the contrast direction we can understand the above as a longitudinal comparison method
• On the other hand, we can treat each string as a single character, and no two adjacent characters are related to each other. Can we see if we can solve this from a dynamic programming point of view?
• First let’s make g(a,b) the longest prefix of a and b. F (x) denotes the longest prefix computed in the array up to x. That is:

• The above formula is a bit complicated. Let’s modify it as follows:

• For the above array we compare the process as follows

public String longestCommonPrefix2(String[] strs) {
    if (strs.length == 0) {
        return "";
    }
    String longest = strs[0];
    for (int i = 1; i < strs.length; i++) {
        if (longest.length() == 0) {
            return "";
        }
        longest = longestFromTwo(longest, strs[i]);
    }
    return longest;
}

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

Four,

• Vertical comparison is the way we usually use it. The execution was pretty good.
• Dynamic programming is probably a little bit out of the way. But it’s really possible to solve this problem with the three axes that I mentioned before. A little bit of deformation will do.
• Both methods have advantages and disadvantages. Radish and vegetables, please

Welcome to pay attention.