首页 > 代码库 > LeetCode之LCP(Longest Common Prefix)问题

LeetCode之LCP(Longest Common Prefix)问题

这个也是简单题目。可是关键在于题意的理解。
题目原文就一句话:Write a function to find the longest common prefix string amongst an array of strings.
题意是给一个字符串数组,找出这个字符串数组中全部字符串的最长公共前缀。


注意是限定的前缀。而不是子串。

所以,直接的解法就是以第一个字符串为基准,逐个比較每一个字符。算法复杂度也显然是O(M*N)。M是字符串的个数,N是最长前缀的长度。

代码例如以下:

class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) {
        int len = strs.size();
        string prefix;
        if(len == 0)return res;
        for(int pos = 0; pos < strs[0].size(); pos++)//最长前缀的长度不超过strs[0].size(),逐个字符的比較
        {
            // 各个字符串相应位置的字符比較
            for(int k = 1; k < len; k++)
            {
                if(strs[k].size() == pos || strs[k][pos] != strs[0][pos])
                    return res;
            }
            prefix.push_back(strs[0][pos]);
        }
        return prefix;
    }
};
<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

LeetCode之LCP(Longest Common Prefix)问题