编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 “”。
输入: [“flower”,“flow”,“flight”]
输出: “fl”
示例 2:
输入: [“dog”,“racecar”,“car”]
输出: “”
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
我的c++代码
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int strsize=strs.size();
if(strsize==0)
return "";
string result="";
sort(strs.begin(),strs.end());//数组从小到大排序
int size=strs[0].length();
for(int i=0;i<size;i++){
char tmp=strs[0][i];
for(int j=1;j<strsize;j++){
if(tmp!=strs[j][i])
return result;
}
result=result+tmp;
}
return result;
}
};
题目还算简单,看了一个耗时比我短的示例,人家的思路是取出第一个string为tmp,与vector中的进行对比,如果不一样就使tmp为原下标为0到(size-2)的值。
看完思路后我实现了一下:
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int strsize=strs.size();
if(strsize==0)
return "";
string tmp=strs[0];
for(int i=1;i<strsize;i++){
//这个循环其实一直在i=1时进行,除非找到了公共前缀
while(strs[i].find(tmp,0)!=0){
tmp=tmp.substr(0,tmp.size()-1);
if(tmp=="")
return "";
}
}
return tmp;
}
};
实现后发现用时和内存消耗差不多,但是代码和别人一样的呀
emmm 后台机制感觉有点问题