Longest common prefix (leetcode question 14)

subject

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

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

Example 1：

Input ：strs = [“flower”,“flow”,“flight”]
Output ：“fl”
Example 2：

Input ：strs = [“dog”,“racecar”,“car”]
Output ：“”
explain ： Input does not have a common prefix .

Tips ：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] It's only made up of lowercase letters

Their thinking

The common idea is to get the first String Traverse the first character of to see whether it conforms to , If it meets the requirements, take out the first String The second character of

The idea of problem solving is
Find the first one String And the second String Public prefix of , Take this public prefix and the third string to take the public prefix , Traverse the last element of the trace in turn

Code

class Solution4 {
    
    public String longestCommonPrefix(String[] strs) {
    
        if (strs == null || strs.length == 0) {
    
            return "";
        }
        String prefix = strs[0];
        int count = strs.length;
        // Compare the two , Get the public prefix , Get the prefix and the next string to find the public prefix 
        for (int i = 1; i < count; i++) {
    
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.length() == 0) {
    
                break;
            }
        }
        return prefix;
    }

    public String longestCommonPrefix(String str1, String str2) {
    
        // First find the minimum traversal length , Take the minimum length of two strings 
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        // Compare from left to right , success index++, If you fail, quit 
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
    
            index++;
        }
        // Returns the public prefix string 
        return str1.substring(0, index);
    }
}

Test code

 public static void main(String[] args) {
    
        Solution4 solution4 = new Solution4();
        String[] strs = {
    "dog", "racecar", "car"};
        System.out.println(solution4.longestCommonPrefix(strs));
    }