Ссылка: → https://leetcode.com/problems/longest-common-prefix/

Вопрос:

Напишите функцию, которая находит самую длинную строку общего префикса среди массива строк.

Если общего префикса нет, вернуть пустую строку "".

Пример 1:

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

Пример 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Ограничения:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] состоит только из строчных английских букв.

Решение:

Здесь мы можем пойти с простым решением:

  1. Сначала найдем самую короткую строку и ее длину.
  2. Во-вторых, мы возьмем самую короткую строку и сопоставим каждый ее символ один за другим со всеми остальными строками.
  3. Как только мы столкнемся с несоответствующим символом, мы выйдем из цикла.

Давайте поймем это по изображениям:

Предположим, мы дали массив, который находится ниже

Теперь применим наше первое условие: найти кратчайшую строку в данном массиве.

Мы получим ABD. Теперь проверьте его длину: она равна 3, поэтому мы создадим цикл for длиной 3 и будем сравнивать символы один за другим.

Теперь, согласно второму условию, мы пытаемся сопоставить символы один за другим. Итак, для первой итерации.

Сначала мы возьмем первое значение индекса первого элемента, которое равно "A", и сохраним его в переменной current,

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

Здесь текущийсимвол 'A' соответствует первому значению индекса другого элемента. поэтому сначала мы сохраним этот соответствующий символ в переменной ‘result’.

Теперь мы берем значение второго индекса первого элемента (first_element[1]), которое равно ‘B’

В приведенном выше примере 'B' также соответствует всем остальным элементам массива, поэтому мы добавим B также в переменную 'result', ' результат' будет "AB".

Теперь мы берем значение третьего индекса первого элемента (first_element[2]), которое равно ‘C’

Здесь «C» доступен не во всех элементах строк, поэтому мы не будем добавлять «C» в переменную «result».

Итак, согласно третьему условию, здесь мы завершаем цикл for и возвращаем переменную "result", которая равна "AB", это и будет нашим ответом.

Код (Java):

Код (Питон):

Сложность времени:

Если n — это длина массива, а m — это длина кратчайшей строки, временная сложность в худшем случае будет O(m × n).

Космическая сложность:

Поскольку мы не используем внутреннюю структуру данных для промежуточных вычислений, объемная сложность будет O(1).

Спасибо, что прочитали эту статью ❤

Если я что-то не так? Позвольте мне в комментариях. Я хотел бы улучшить.

Хлопайте 👏 Если вам поможет эта статья.