LeetCode14 Longest Common Prefix

题意:

Write a function to find the longest common prefix string amongst an array of strings. (Easy)

这两天实验室项目太忙了, 老板各种活,只能挑着先水几道easy题,这两个题是昨天做的没来得及写总结。

分析:

暴力的想法遍历比较一下就行,注意遍历的始末位置。优化的话改天再看看discuss

代码:

 class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string result;
if (strs.size() == ) {
return result;
}
int minLength = 0x7FFFFFFF;
for (int i = ; i < strs.size(); ++i) {
int si = strs[i].size();
minLength = min(minLength, si);
} for (int i = ; i < minLength; ++i) {
int flag = ;
for (int j = ; j < strs.size() - ; ++j) {
if (strs[j][i] != strs[j + ][i]) {
flag = ;
break;
}
}
if (flag == ) {
result += strs[][i];
}
if (flag == ) {
break;
}
}
return result;
}
};

8.6更新:

上面的还是不删除了,算法上这个简单题应该没啥优化的了,无非是另一种方法拿第一个字符串以此与后续求公共前缀;

但是!当初这个代码写的真是太长太丑了...有一些可以优化代码的地方,比如

1.  flag其实没用,不满足情况就直接返回结果就行了;

2.  不要多走一遍求最小来作为遍历范围了,中间加一个判断语句就行;

3.  不用sting的+=,改用一个length最后再substr感觉效率上会高一点;(在leetcode跑的并没变化...)

更新后代码:

 class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int length = ;
if (strs.size() == ) {
return "";
}
for (int i = ; i < strs[].size(); ++i) {
for (int j = ; j < strs.size() - ; ++j) {
if (strs[j].size() == i|| strs[j][i] != strs[j + ][i]) {
return strs[].substr(,length);
}
}
length++;
}
return strs[].substr(,length);
}
};
上一篇:关于ios手机游览器针对overflow:hidden设置无效的解决办法


下一篇:WinServer远程部署系统打包批处理文件