Насколько такое решение можно назвать хорошим ? Какое решение этой задачи можно считать эталонным?

Question

Задача:

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "".

Пример :

Input: strs = ["flower","flow","flight"]
Output: "fl"

Моё решение:

string longestCommonPrefix(vector<string>& strs) 
    {
      
       std::sort(strs.begin(),strs.end(),
        [](const string& a, const string& b)
        { return a.length() < b.length(); });
        
        std::string answer = strs[0];
        if(strs.size() == 0)
            return "";
        std::size_t found;
        for (int i = 1; i < strs.size(); ++i)
        {
            found = strs[i].find(answer);
            if (found != 0)
            {
                answer = answer.substr(0,answer.length()-1);
                i = 0;
                continue;
            }
        }
        
        return answer;
    }

Серивс показал следующую оценку этого решения: В целом, вроде бы, неплохо. Но хотелось бы узнать насколько такое решение можно назвать хорошим? есть ли у такого решения название ? (название алгоритма). Ну и собственно какой алгоритм для решения такой задачи можно назвать эталонным?

Answer 1

Ну, у меня вот это решение, основанное на простом переборе всех символов всех строк, начиная с первого (ну, и + некоторые частные случаи):

string longestCommonPrefix(vector<string>& strs)
{
    const int N = strs.size();
    if (N == 0) return "";
    if (N == 1) return strs[0];
    int l = 0;
    string s;
    for(;;++l)
    {
        char c = strs[0][l];
        if (c == 0) return s;
        bool ok = true;
        for(int i = N; i-->1;)
            if (strs[i][l] != c) { ok = false; break;}
        if (!ok) return s; else s += c;
    }
}

сказало, что

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Longest Common Prefix.
Memory Usage: 9.2 MB, less than 77.26% of C++ online submissions for Longest Common Prefix.

Но какое решение идеальное — я не знаю...

OK, чтоб снять лишние вопросы...

string longestCommonPrefix(vector<string>& strs)
{
    const int N = strs.size();
    if (N == 0) return "";
    if (N == 1) return strs[0];
    int l = 0;
    string s;
    s.reserve(strs[0].size());
    for(;;++l)
    {
        char c = strs[0][l];
        if (c == 0) return s;
        bool ok = true;
        for(int i = N; i-->1;)
            if (strs[i][l] != c) { ok = false; break;}
        if (!ok) return s; else s.push_back(c);
    }
}

Забавно, что это решение еще и уменьшило количество используемой памяти:

Answer 2

NB: этот ответ существенно обновлён.

Ответ на собственно вопрос

Ваш код обращается к первой строке до того как вы проверили размер вектора. LeetCode не проверяет пустой набор?

Сброс индекса i = 0; в теле цикла может привести к очень медленной (квадратичной) работе на специальных примерах. Но на LeetCode их нет.

Добавьте в ваше решение проверку

        if (strs.size() == 1)
            return strs[0];

это может сделать ваше решение идеальным (0ms). Видимо, есть отдельный тест с только одной длинной строкой.

Без сортировки можно обойтись. Опять таки из-за сортировки может снизится производительность на некоторых примерах, которых нет на LeetCode. Вместо сортировки отыщите самую короткую строку и поменяйте её с первой.

Вообще, на LeetCode дырявые тесты на этой задаче.

Идеальное решение?

Решение ниже LeetCode иногда считает идеальным (0ms), а я считаю таким всегда. Сперва определим длину самой короткой строки. Дальше этой длины ходить не зачем. Проверим по столбцам что символы одинаковы. При обнаружении первого отличия выдадим ответ. К каждому символу обращение идёт только один раз:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        const vector<string>::size_type n = strs.size();
        if (n == 0) {
            return "";
        }
        if (n == 1) {
            return strs[0];
        }

        size_t min_size = strs[0].size();
        for (vector<string>::size_type j = 1; j < n; ++j) {
            min_size = std::min(min_size, strs[j].size());
        }

        for (size_t i = 0; i < min_size; ++i) {
            const char c = strs[0][i];
            for (vector<string>::size_type j = 1; j < n; ++j) {
                if (strs[j][i] != c) {
                    return strs[0].substr(0, i);
                }
            }
        }
        return strs[0].substr(0, min_size);
    }
};

БЛОГ НА HUSL

Насколько такое решение можно назвать хорошим ? Какое решение этой задачи можно считать эталонным?

Ответы (2 шт):

Ответ на собственно вопрос

Идеальное решение?