Topic link

Leetcode-cn.com/problems/lo…

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:"flower"."flow"."flight"] output:"fl"
Copy the code

Example 2:

Input:"dog"."racecar"."car"] output:""Explanation: The input does not have a common prefix.Copy the code

Description:

All inputs contain only lowercase letters A-z.

The problem solving scheme

Train of thought

  • Tag: string
  • If the string array length is 0, the public prefix is empty
  • Initialize with the value of the longest public prefix ans as the first string
  • Iterate through the following strings and compare them to ans in turn, finding the common prefix in pairs. The result is the longest common prefix
  • If ans is empty during the lookup, there is no direct return for the common prefix
  • Time complexity: O(s), where S is the sum of the length of all strings

code

  • Java version
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;
        }
        returnans; }}Copy the code
  • The JavaScript version
/** * @param {string[]} strs * @return {string} */
var longestCommonPrefix = function(strs) {
    if(strs.length == 0) 
        return "";
    let ans = strs[0];
    for(let i =1; i<strs.length; i++) {let j=0;
        for(; j<ans.length && j < strs[i].length; j++) {if(ans[j] ! = strs[i][j])break;
        }
        ans = ans.substr(0, j);
        if(ans === "")
            return ans;
    }
    return ans;
};
Copy the code

Draw solution

Background reply “algorithm”, join every day algorithm group feel algorithm directly to the soul, welcome to click on and forward