0 added
0 removed
Original
2026-01-01
Modified
2026-02-21
1
<p><a>#статьи</a></p>
1
<p><a>#статьи</a></p>
2
<ul><li>24 авг 2022</li>
2
<ul><li>24 авг 2022</li>
3
<li>0</li>
3
<li>0</li>
4
</ul><h2>Задача: ищем самый длинный общий префикс у элементов массива строк</h2>
4
</ul><h2>Задача: ищем самый длинный общий префикс у элементов массива строк</h2>
5
<p>Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня ищем общий префикс в массиве строк.</p>
5
<p>Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня ищем общий префикс в массиве строк.</p>
6
<p>Иллюстрация: Polina Vari для Skillbox Media</p>
6
<p>Иллюстрация: Polina Vari для Skillbox Media</p>
7
<p>Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.</p>
7
<p>Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.</p>
8
<p><strong>Условие.</strong>Необходимо написать функцию, которая находит самый длинный общий префикс среди элементов массива строк. Если такого префикса нет, программа должна вернуть пустую строку.</p>
8
<p><strong>Условие.</strong>Необходимо написать функцию, которая находит самый длинный общий префикс среди элементов массива строк. Если такого префикса нет, программа должна вернуть пустую строку.</p>
9
Ввод: strs = ["flower", "flow", "flight"] Вывод: "fl"Ввод: strs = ["dog", "racecar", "car"] Вывод: "" // Пояснение: у этих строк нет общего префикса.<p>Решить эту задачу самостоятельно и на разных языках программирования можно на <a>LeetCode</a>. Наше решение взято из Telegram-канала Сергея<a>Cracking code interview</a>.</p>
9
Ввод: strs = ["flower", "flow", "flight"] Вывод: "fl"Ввод: strs = ["dog", "racecar", "car"] Вывод: "" // Пояснение: у этих строк нет общего префикса.<p>Решить эту задачу самостоятельно и на разных языках программирования можно на <a>LeetCode</a>. Наше решение взято из Telegram-канала Сергея<a>Cracking code interview</a>.</p>
10
<p><strong>Решение</strong></p>
10
<p><strong>Решение</strong></p>
11
<p>Чтобы решить эту задачу, мы будем использовать принцип "скользящего окна". Его суть в том, что мы берём две строки и начинаем посимвольно сравнивать их, как бы смотря на них через окно.</p>
11
<p>Чтобы решить эту задачу, мы будем использовать принцип "скользящего окна". Его суть в том, что мы берём две строки и начинаем посимвольно сравнивать их, как бы смотря на них через окно.</p>
12
<p>Для нашей задачи это самый простой и очевидный метод решения. Мы возьмём два указателя - начала и конца - и будем перемещать их в зависимости от условий: нашли или не нашли одинаковую последовательность символов.</p>
12
<p>Для нашей задачи это самый простой и очевидный метод решения. Мы возьмём два указателя - начала и конца - и будем перемещать их в зависимости от условий: нашли или не нашли одинаковую последовательность символов.</p>
13
<p>На старте алгоритма первая строка массива будет считаться общим префиксом. В процессе мы будем сравнивать её с другими строками и отрезать с конца символы, которые не совпадают. И так с каждой строкой массива.</p>
13
<p>На старте алгоритма первая строка массива будет считаться общим префиксом. В процессе мы будем сравнивать её с другими строками и отрезать с конца символы, которые не совпадают. И так с каждой строкой массива.</p>
14
<p>Полный алгоритм такой:</p>
14
<p>Полный алгоритм такой:</p>
15
<ul><li>Сначала проверяем размер массива: если массив пустой, то и общий префикс - пустая строка. А если в массиве только один элемент, то он и будет общим префиксом.</li>
15
<ul><li>Сначала проверяем размер массива: если массив пустой, то и общий префикс - пустая строка. А если в массиве только один элемент, то он и будет общим префиксом.</li>
16
<li>В остальных случаях берём первую строку массива и принимаем её за самый длинный общий префикс.</li>
16
<li>В остальных случаях берём первую строку массива и принимаем её за самый длинный общий префикс.</li>
17
<li>Ставим два указателя: один будет следить за индексом последнего символа, который совпал с нашим общим префиксом, а второй будет перемещаться по строкам посимвольно.</li>
17
<li>Ставим два указателя: один будет следить за индексом последнего символа, который совпал с нашим общим префиксом, а второй будет перемещаться по строкам посимвольно.</li>
18
<li>Перебираем элементы массива, начиная со второго - сравниваем символы в этом элементе с символами общего префикса. Если символы равны, увеличиваем индекс общего префикса на один, если нет - просто идём дальше.</li>
18
<li>Перебираем элементы массива, начиная со второго - сравниваем символы в этом элементе с символами общего префикса. Если символы равны, увеличиваем индекс общего префикса на один, если нет - просто идём дальше.</li>
19
<li>После проверки очередной строки массива отрезаем от общего префикса лишние символы - по индексу, который сохранён в нашем указателе.</li>
19
<li>После проверки очередной строки массива отрезаем от общего префикса лишние символы - по индексу, который сохранён в нашем указателе.</li>
20
</ul><p>Вот как этот алгоритм будет реализован на Java:</p>
20
</ul><p>Вот как этот алгоритм будет реализован на Java:</p>
21
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; }<p><strong>Результаты</strong></p>
21
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; }<p><strong>Результаты</strong></p>
22
<p><strong>Временная сложность:</strong>O(n) - так как мы перебирали все элементы массива.</p>
22
<p><strong>Временная сложность:</strong>O(n) - так как мы перебирали все элементы массива.</p>
23
<p><strong>Ёмкостная сложность:</strong>O(1) - нам нужно заранее определённое количество места в памяти (максимальный размер памяти - длина первого слова в массиве).</p>
23
<p><strong>Ёмкостная сложность:</strong>O(1) - нам нужно заранее определённое количество места в памяти (максимальный размер памяти - длина первого слова в массиве).</p>
24
<a>Научитесь: Профессия Java-разработчик + ИИ Узнать больше</a>
24
<a>Научитесь: Профессия Java-разработчик + ИИ Узнать больше</a>