Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Topic describes

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: STRS = ["flower","flow","flight"] Output: "FL" Example 2: Input: STRS = ["dog","racecar","car"] Output: "" Description: The input does not have a public prefix. Source: LeetCode Link: https://leetcode-cn.com/problems/longest-common-prefix Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

• Today’s algorithm topic is string manipulation. And they want to figure out the longest common prefix. The naive solution is to compare adjacent strings and iterate over each string in the string array. For each string iterated, update the longest public prefix. When all strings are iterated, the longest public prefix in the string array is obtained.

Through the code

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int n = strs.length;
        if (n == 0) {
            return "";
        }

        String prefix = strs[0];
        for (int i = 1; i < n; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.length() == 0) {
                break; }}return prefix;
        
    }

    private String longestCommonPrefix(String str1, String str2) {
        int minLength = Math.min(str1.length(), str2.length());
        int i = 0;
        while (i < minLength && str1.charAt(i) == str2.charAt(i)) {
            i++;
        }
        return str1.substring(0, i); }}Copy the code

conclusion

• Naive algorithm thinking is relatively clear, the main investigation is the string function familiar degree. The time complexity of the naive algorithm is O(n * n), the space complexity is O(1).
• Adhere to the algorithm of the day, come on!