The title

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”

Example 2: Input: [“dog”,”racecar”,”car”] Output: “”

Thinking a

The simplest idea is to compare each string vertically.

A code

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        int length = strs[0].length();
        int count = strs.length;
        for (int i = 0; i < length; i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < count; j++) {
                if (i >= strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}
Copy the code

Time complexity: O(MN). M represents the length of the string array and n represents the average length of each string.

Space complexity: O(1).

Idea 2

Horizontal comparison: compute the longest common substring in pairs, then compute the longest common substring against other strings.

Code 2

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        String common = strs[0];
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            common = common(common, strs[i]);
        }
        return common;
    }
​
    private String common(String str1, String str2) {
        int length = str1.length();
        for (int i = 0; i < length; i++) {
            char c = str1.charAt(i);
            if (i == str2.length() || str2.charAt(i) != c) {
                return str1.substring(0, i);
            }
        }
        return str1;
    }
}
Copy the code

Time complexity: O(Mn)

Space complexity: O(1)

Hard advertising

Welcome to the public account: Double6