Two solutions, which one is better?


  • 2
    R

    Solution 1:

    class Solution {
    public:
        string longestCommonPrefix(vector<string>& strs) {
            if(strs.empty()) {
                return "";
            }
            sort(strs.begin(), strs.end());
            int count = 0;
            while(true) {
                if(count >= strs[0].size() || (strs[0][count] != strs[strs.size() - 1][count])) {
                    break;
                }
                count++;
            }
            return strs[0].substr(0, count);
        }
    };
    

    Solution 2:

    class Solution {
    public:
        string longestCommonPrefix(vector<string>& strs) {
            if(strs.empty()) {
                return "";
            }
            int count = 0;
            while(true) {
                for(int i = 0; i < strs.size(); i++) {
                    if(count >= strs[i].size() || (i > 0 && strs[i][count] != strs[i - 1][count])) {
                        return strs[0].substr(0, count);
                    }
                }
                count++;
            }
            return strs[0].substr(0, count);
        }
    };
    

    Can anyone explain which algorithm is a little better?


  • 0
    R

    I personally think the latter(without sorting) is better. The sorting of numbers takes O(nlogn), but the sorting of strings should take O(nlogn * k), while k is the average length of these strings, since you need to compare strings character by character to determine which one is smaller.


  • 0
    R

    @rekozh Yes, your are right. BTW: in this problem, it might be possible to use count sort. Then they will have same performance.


  • 0
    6

    hi,i don't know why you want to sort it....
    c++ 's sort is sort by what? ascll or length?


  • 0
    R
    This post is deleted!

  • 0
    R

    @692235635 The purpose of sorting is to just compare the first string and last string, instead of comparing the first string with all other strings.
    In C++, the sort function use ASCII code to sort a string by default. But the sorting is also related with length. For the detail, you may check a C++ reference book. BTW: you can define your own sorting rule.


  • 0
    6

    @rpfly3 thanks!your answer is really helpful to me!


  • 0
    R

    @692235635 You are very welcome. I am happy it helps.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.