当前位置：网站首页>Longest public prefix of leetcode

Longest public prefix of leetcode

2022-07-02 20:35:00 【wx58c8fa5d0b356】

List of articles

LeetCode The longest public prefix of the brush question

Title Description

Example

Problem solving

Ideas
Code

LeetCode The longest public prefix of the brush question

Title Description

Write a function to find the longest common prefix in the string array .

If no common prefix exists , Returns an empty string “”.

Example

Example 1:

Input : [“flower”,“flow”,“flight”]

Output : “fl”

Example 2:

Input : [“dog”,“racecar”,“car”]

Output : “”

explain : Input does not have a common prefix .

explain :

All inputs contain only lowercase letters a-z .

Problem solving

Ideas

Take any character , from 0 Start to intercept string , See whether the interception result is the same as that of other strings .

If it's not the same , What I intercepted before is the longest public prefix .

Note that the characters you choose are not necessarily the shortest , To prevent the index from crossing the boundary , It needs to be verified .

Code

       
        public static String longestCommonPrefix2(String[] strs) {
        
        //  Visibility verification 
        
        if (strs.length == 0) {
        
            return "";
        
        }
        

        
        if (strs.length == 1) {
        
            return strs[0];
        
        }
        

        
        //  answer 
        
        String ans = "";
        

        
        for (int i = 0; i < strs[0].length(); i++) {
        
            String substring = strs[0].substring(0, i + 1);
        

        
            for (int j = 1; j < strs.length; j++) {
        

        
                if (substring.length() > strs[j].length()) {
        
                    return ans;
        
                }
        

        
                if (!substring.equals(strs[j].substring(0, i + 1))) {
        
                    return ans;
        
                }
        
            }
        
            ans = substring;
        
        }
        
        return ans;
        
    }
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.
        9.
        10.
        11.
        12.
        13.
        14.
        15.
        16.
        17.
        18.
        19.
        20.
        21.
        22.
        23.
        24.
        25.
        26.
        27.
        28.
        29.
        30.

A regular matching version is attached below , It's a little slow , It is not recommended to adopt

       
        public static String longestCommonPrefix(String[] strs) {
        

        
        //  Shortest character 
        
        String shortest = strs[0];
        
        for (int i = 1; i < strs.length; i++) {
        
            if (strs[i].length() < shortest.length()) {
        
                shortest = strs[i];
        
            }
        
        }
        
        //  One is "" The result is ""
        
        if (shortest.length() == 0) {
        
            return "";
        
        }
        

        
        for (int i = 0; i < shortest.length(); i++) {
        
            String regex = "^" + shortest.substring(0, i + 1) + "\\w*$";
        

        
            for (String element : strs) {
        
                if (!Pattern.matches(regex, element)) {
        
                    return shortest.substring(0, i);
        
                }
        
            }
        
        }
        
        return shortest;
        
    }
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.
        9.
        10.
        11.
        12.
        13.
        14.
        15.
        16.
        17.
        18.
        19.
        20.
        21.
        22.
        23.
        24.
        25.