This is the 11th day of my participation in Gwen Challenge

preface

The longest common prefix in question 14 is shown below:

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.

A, thinking

This one is short and easy to understand. The meaning of the question is relatively clear, and there is no need for a simple summary.

Mainly talk about the realization of the idea, mainly divided into the following steps:

  • Select the first string from an array of strings and traverse the string from left to right (optional in example 1)"flower"And traverses from left to right)
  • When it is found that the current character traversed does not exist in another string, the result is returned (as traversed in example 1)"flower"Is traversed to the character"o"Found in the"flight"If not, you can stop traversal and return the result"fl")

Second, the implementation

This one problem according to the steps summed up in front can, two layers of circulation can solve the problem!

Code implementation

Because of the concatenation of strings, we use StringBuilder to prevent frequent creation of objects in the constant pool. (For example, if the string array is [“ab”, “a”], it will be out of bounds to look for the character in the string “A” when iterating over character B)

    public String longestCommonPrefix(String[] strs) {
        // Special circumstances
        if (strs.length == 0)
            return "";
        StringBuilder ret = new StringBuilder();
        for (int i=0; i<strs[0].length(); i++) {
            char tempStr = strs[0].charAt(i);
            for (int j=1 ; j<strs.length; j++) {
                String temp = strs[j];
                // Out of bounds or characters are not equal
                if (i + 1> temp.length() || tempStr ! = temp.charAt(i)) {return ret.toString();
                }
            }
            ret.append(tempStr);
        }
        return ret.toString();
    }
Copy the code

The test code

The test code is shown below:

    public static void main(String[] args) {
        String ret = new Number14().longestCommonPrefix(new String[] {"ab"."a"});
        System.out.println(ret);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥