[leetcode] 14. Longest public prefix

14、 The longest common prefix

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 ：

This question is not difficult , Just use the most popular solution , The strings in the array are compared one by one , Same take out , Different pass Just drop it .

• label ： Linked list
• When the string array length is 0 The public prefix is empty , Go straight back to
• Make the longest public prefix ans The value of is the first string , To initialize
• Traversing the following string , In turn, match it with ans Compare , Find the common prefix , The end result is the longest common prefix
• If during the search ans Empty situation , Then the public prefix does not exist and directly returns
• Time complexity ：O(s)O(s),s For the sum of the length of all strings

Reference code ：

class Solution {
    
    public String longestCommonPrefix(String[] strs) {
    
        if(strs.length == 0) 
            return "";
        String ans = strs[0];
        for(int i =1;i<strs.length;i++) {
    
            int j=0;
            for(;j<ans.length() && j < strs[i].length();j++) {
    
                if(ans.charAt(j) != strs[i].charAt(j))
                    break;
            }
            ans = ans.substring(0, j);
            if(ans.equals(""))
                return ans;
        }
        return ans;
    }
}