14.Longest Common Prefix¶
Tags: Easy
String
Links: https://leetcode.com/problems/longest-common-prefix/
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string ""
.
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:
All given inputs are in lowercase letters a-z
.
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
if (strs.size() == 0) return "";
if (strs.size() == 1) return strs[0];
int len = INT_MAX;
int n = strs[0].size();
int tmpLen = 0;
for (int i = 1; i < strs.size(); ++i) {
tmpLen = 0;
for (int j = 0; j < strs[i].size(); ++j) {
if (j < n && tmpLen < len && strs[0][j] == strs[i][j])
++tmpLen;
else break;
}
if (tmpLen == 0) {
len = 0;
break;
}
else len = min(tmpLen, len);
}
return strs[0].substr(0, len);
}
};