首页 > 其他 > 详细

【Longest Common Prefix】cpp

时间:2015-05-10 18:53:09      阅读:176      评论:0      收藏:0      [点我收藏+]

题目:

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()==0 ) return "";
            std::string tmp_str = strs[0];
            for ( size_t i = 1; i < strs.size(); ++i )
            {
                size_t j = 0;
                for ( ; j < std::min(tmp_str.size(), strs[i].size()); ++j ) 
                    if ( tmp_str[j]!=strs[i][j] ) break;
                tmp_str = tmp_str.substr(0,j);
            }
            return tmp_str;
    }
};

tips:

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

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

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

 

【Longest Common Prefix】cpp

原文:http://www.cnblogs.com/xbf9xbf/p/4492704.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!