cpp-leetcode/longestCommonPrefix.cpp at main · neteroster/cpp-leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 1st version
// O(n * m)

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string result = "";
        int i = 0;
        char tmp = strs[0][0];

        while(true)
        {

            for (auto &e : strs)
            {
                if (e.begin() + i == e.end())
                {
                    return result;
                }
                if (e[i] != tmp) return result;
            }
            result += strs[0][i];
            i++;
            tmp = strs[0][i];

        }
    }
};

// 2st version O(nlogn + m)

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        sort(strs.begin(), strs.end()); // O(nlogn)

        auto beg = strs.begin();
        auto ed = strs.end() - 1;

        int min_len = beg->size() < ed->size() ?
            beg->size() : ed->size();

        int i;
        for (i = 0; i < min_len && (*beg)[i] == (*ed)[i]; i++);

        return strs.begin()->substr(0, i);
    }

};