Задача: ищем самый длинный общий префикс у элементов массива строк
2026-02-21 15:33 Diff
https://skillbox.ru/media/code/zadacha-ishchem-samyy-dlinnyy-obshchiy-prefiks-u-elementov-massiva-strok/

#статьи

  • 24 авг 2022
  • 0

Задача: ищем самый длинный общий префикс у элементов массива строк

Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня ищем общий префикс в массиве строк.

Иллюстрация: Polina Vari для Skillbox Media

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

Условие. Необходимо написать функцию, которая находит самый длинный общий префикс среди элементов массива строк. Если такого префикса нет, программа должна вернуть пустую строку.

Ввод: strs = ["flower", "flow", "flight"] Вывод: "fl"Ввод: strs = ["dog", "racecar", "car"] Вывод: "" // Пояснение: у этих строк нет общего префикса.

Решить эту задачу самостоятельно и на разных языках программирования можно на LeetCode. Наше решение взято из Telegram-канала Сергея Cracking code interview.

Решение

Чтобы решить эту задачу, мы будем использовать принцип «скользящего окна». Его суть в том, что мы берём две строки и начинаем посимвольно сравнивать их, как бы смотря на них через окно.

Для нашей задачи это самый простой и очевидный метод решения. Мы возьмём два указателя — начала и конца — и будем перемещать их в зависимости от условий: нашли или не нашли одинаковую последовательность символов.

На старте алгоритма первая строка массива будет считаться общим префиксом. В процессе мы будем сравнивать её с другими строками и отрезать с конца символы, которые не совпадают. И так с каждой строкой массива.

Полный алгоритм такой:

  • Сначала проверяем размер массива: если массив пустой, то и общий префикс — пустая строка. А если в массиве только один элемент, то он и будет общим префиксом.
  • В остальных случаях берём первую строку массива и принимаем её за самый длинный общий префикс.
  • Ставим два указателя: один будет следить за индексом последнего символа, который совпал с нашим общим префиксом, а второй будет перемещаться по строкам посимвольно.
  • Перебираем элементы массива, начиная со второго — сравниваем символы в этом элементе с символами общего префикса. Если символы равны, увеличиваем индекс общего префикса на один, если нет — просто идём дальше.
  • После проверки очередной строки массива отрезаем от общего префикса лишние символы — по индексу, который сохранён в нашем указателе.

Вот как этот алгоритм будет реализован на Java:

public String longestCommonPrefix(String[] strs) { if(strs.length == 0){ return ""; } if (strs.length == 1){ return strs[0]; } String rez = strs[0]; for(int i = 1; i < strs.length; i ++){ String cur = strs[i]; int reader = 0; int lastCommon = 0; while(reader < rez.length() && reader < cur.length()){ if(rez.charAt(reader) == cur.charAt(reader)){ lastCommon ++; } else { break; } reader++; } rez = rez.substring(0, lastCommon); } return rez; }

Результаты

Временная сложность: O(n) — так как мы перебирали все элементы массива.

Ёмкостная сложность: O(1) — нам нужно заранее определённое количество места в памяти (максимальный размер памяти — длина первого слова в массиве).

Научитесь: Профессия Java-разработчик + ИИ Узнать больше