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