【Longest Common Prefix】cpp

题目:

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

代码:

class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if ( strs.size()== ) return "";
std::string tmp_str = strs[];
for ( size_t i = ; i < strs.size(); ++i )
{
size_t j = ;
for ( ; j < std::min(tmp_str.size(), strs[i].size()); ++j )
if ( tmp_str[j]!=strs[i][j] ) break;
tmp_str = tmp_str.substr(,j);
}
return tmp_str;
}
};

tips:

空间复杂度O(n1),时间复杂度O(n1+n2...)

strs中的每个string串依次两两比较,保留下这一次比较得出的公共前缀为tmp_str;下次再比较时,可以用上次得到的公共前缀作为目标字符串。

这个解法的好处就是代码比较consice,但空间复杂度和时间复杂度其实都不是最优的。

=====================================================

第二次过这道题,自己写出来了代码,调了两次AC了。

class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if ( strs.size()== ) return "";
if ( strs.size()== ) return strs[];
string common_pre = strs[];
for ( int i=; i<strs.size(); ++i )
{
if ( common_pre.size()== ) break;
int common_len = min( common_pre.size(), strs[i].size());
for ( int j= ;j<min( common_pre.size(), strs[i].size()); ++j )
{
if ( common_pre[j]!=strs[i][j] )
{
common_len = j;
break;
}
}
common_pre = common_pre.substr(,common_len);
}
return common_pre;
}
};
上一篇:【Longest Consecutive Sequence】cpp


下一篇:python 字符串 string