首页 > 代码库 > Longest Common Prefix -- leetcode

Longest Common Prefix -- leetcode

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 "";

        string prefix;
        for (size_t i=0; i<strs[0].size(); i++) {
                const char ch = strs[0][i];
                int j = 1;
                while (j < strs.size() &&
                        ch == strs[j][i])
                                ++j;

                if (j == strs.size())
                        prefix.append(1, ch);
                else
                        break;
        }

        return prefix;
    }
};


方法二,以第一个字符串作为初始值,横向推进,逐步裁剪。

class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) {
        if (!strs.size()) return "";

        string prefix = strs[0];
        for (size_t i=1; i<strs.size(); i++) {
                size_t j = 0;
                while (j < prefix.size() &&
                        j <strs[i].size() &&
                        prefix[j] == strs[i][j])
                        ++j;

                prefix.erase(j);
                if (!prefix.size())
                        break;
        }

        return prefix;
    }
};

感觉这两个方法各有各的适用之地吧,是否没有明显好坏之分。

Longest Common Prefix -- leetcode