1. The subject

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]
  • Contains only lowercase English letters

2. The answer

Idea 1:

  • Caches the prefix of the first string
  • Loop over whether the subsequent string contains the value and saves the maximum ordinal number
  • The end condition

The code is as follows:

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length <= 0) {
            return "";
        }
​
        String first = strs[0];
        List<String> preList = new ArrayList<>(first.length());
        for (int i = 0; i < first.length(); i++) {
            preList.add(first.substring(0, i + 1));
        }
​
        int max = -1;
        for (int i = 1; i < strs.length; i++) {
            int tmpMax = -1;
            String str = strs[i];
            for (int j = 0; j < preList.size(); j++) {
                if (str.startsWith(preList.get(j))) {
                    tmpMax = i;
                } else {
                    break; }}if (tmpMax == -1) {// No successful prefix is matched
                max = -1;
                break;
            }
​
            if (max == -1) {
                max = tmpMax;
            } else{ max = Math.min(max, tmpMax); }}return max == -1 ? "": preList.get(max); }}Copy the code

Time complexity

Traversal the first element is O(m), loop nesting is O(nm), and in general it’s O(m+mn).

Submit the results

This is a messy way to write. Try the following steps:

  • Loop over the string to see if it starts with the first element
  • If yes, continue until the loop ends
  • No, shrink the first element by one
public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length <= 0) {
            return "";
        }
​
        String publicStr = strs[0];
        while(publicStr.length() ! =0) {
            boolean flag = true;
            for (int i = 1; i < strs.length; i++) {
                if(! strs[i].startsWith(publicStr)) { publicStr = publicStr.substring(0, publicStr.length() - 1);
                    flag = false;
                    break; }}if (flag) {
                returnpublicStr; }}return ""; }}Copy the code

Submit the results

The solution is basically the same as above, at least a little bit simpler code, squeeze again, there are other solutions, wait for higher level later gg