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>1 сен 2022</li>
2
<ul><li>1 сен 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>Даны две строки -<strong>s</strong>и <strong>t</strong>. Нужно проверить их изоморфность.</p>
8
<p><strong>Условие.</strong>Даны две строки -<strong>s</strong>и <strong>t</strong>. Нужно проверить их изоморфность.</p>
9
<p>Пояснение: строки<strong>s</strong>и <strong>t</strong>называются изоморфными, если все вхождения каждого символа строки<strong>s</strong>можно последовательно заменить другим символом и получить строку<strong>t</strong>. Порядок символов при этом должен сохраняться, а замена - быть уникальной. Так, два разных символа строки<strong>s</strong>нельзя заменить одним и тем же символом из строки<strong>t</strong>, а вот одинаковые символы в строке<strong>s</strong>должны заменяться одним и тем же символом. Звучит сложно, поэтому просто посмотрите примеры ввода и вывода :)</p>
9
<p>Пояснение: строки<strong>s</strong>и <strong>t</strong>называются изоморфными, если все вхождения каждого символа строки<strong>s</strong>можно последовательно заменить другим символом и получить строку<strong>t</strong>. Порядок символов при этом должен сохраняться, а замена - быть уникальной. Так, два разных символа строки<strong>s</strong>нельзя заменить одним и тем же символом из строки<strong>t</strong>, а вот одинаковые символы в строке<strong>s</strong>должны заменяться одним и тем же символом. Звучит сложно, поэтому просто посмотрите примеры ввода и вывода :)</p>
10
Ввод: s = "egg", t = "add" Вывод: trueВвод: s = "foo", t = "bar" Вывод: falseВвод: s = "paper", t = "title" Вывод: true<p>Решить эту задачу самостоятельно и на разных языках программирования можно на <a>LeetCode</a>. Наше решение взято из Telegram-канала Сергея<a>Cracking code interview</a>.</p>
10
Ввод: s = "egg", t = "add" Вывод: trueВвод: s = "foo", t = "bar" Вывод: falseВвод: s = "paper", t = "title" Вывод: true<p>Решить эту задачу самостоятельно и на разных языках программирования можно на <a>LeetCode</a>. Наше решение взято из Telegram-канала Сергея<a>Cracking code interview</a>.</p>
11
<p><strong>Решение</strong></p>
11
<p><strong>Решение</strong></p>
12
<p>Чтобы решить эту задачу, нам нужно создать два массива. Каждый массив мы будем использовать как словарь со всеми возможными символами, которые находятся в ASCII-таблице. Так мы сократим количество вариантов всего до 256 символов и упростим задачу. А вот если бы мы решали её, используя кодировку Unicode, нам бы понадобился массив побольше.</p>
12
<p>Чтобы решить эту задачу, нам нужно создать два массива. Каждый массив мы будем использовать как словарь со всеми возможными символами, которые находятся в ASCII-таблице. Так мы сократим количество вариантов всего до 256 символов и упростим задачу. А вот если бы мы решали её, используя кодировку Unicode, нам бы понадобился массив побольше.</p>
13
<p>Массивы нужны, чтобы сопоставлять символы из одной строки с символами из другой. Алгоритм работает так:</p>
13
<p>Массивы нужны, чтобы сопоставлять символы из одной строки с символами из другой. Алгоритм работает так:</p>
14
<ul><li>Сначала мы создаём два массива и заполняем все элементы значением "-1". Это нужно, чтобы в будущем понять, где у нас незанятые элементы.</li>
14
<ul><li>Сначала мы создаём два массива и заполняем все элементы значением "-1". Это нужно, чтобы в будущем понять, где у нас незанятые элементы.</li>
15
<li>Проходим по символам внутри строк и превращаем каждый символ в ASCII-код - число от 0 до 255. На каждой итерации у нас будет по два таких числа: для строки<strong>s</strong>и <strong>t</strong>.</li>
15
<li>Проходим по символам внутри строк и превращаем каждый символ в ASCII-код - число от 0 до 255. На каждой итерации у нас будет по два таких числа: для строки<strong>s</strong>и <strong>t</strong>.</li>
16
<li>Затем проверяем, что коды этих символов не заняты в обоих массивах. Если это так, то записываем в первый массив код символа строки<strong>t</strong>, а во второй - код символа строки<strong>s</strong>.</li>
16
<li>Затем проверяем, что коды этих символов не заняты в обоих массивах. Если это так, то записываем в первый массив код символа строки<strong>t</strong>, а во второй - код символа строки<strong>s</strong>.</li>
17
<li>Если один из элементов массива уже занят кодом, значит, строки не будут изоморфными.</li>
17
<li>Если один из элементов массива уже занят кодом, значит, строки не будут изоморфными.</li>
18
</ul><p>Вот как этот алгоритм будет реализован на Java:</p>
18
</ul><p>Вот как этот алгоритм будет реализован на Java:</p>
19
public boolean isIsomorphic(String s, String t) { int[] sChar = new int[256]; int[] tChar = new int[256]; Arrays.fill(sChar, -1); Arrays.fill(tChar, -1); for(int i = 0; i < s.length(); i++){ int sCharIdx = s.charAt(i); int stCharIdx = t.charAt(i); if (sChar[sCharIdx] == -1 && tChar[stCharIdx] == -1){ sChar[sCharIdx] = stCharIdx; tChar[stCharIdx] = sCharIdx; } else if (sChar[sCharIdx] != stCharIdx || tChar[stCharIdx] != sCharIdx) { return false; } } return true; }<p><strong>Результаты</strong></p>
19
public boolean isIsomorphic(String s, String t) { int[] sChar = new int[256]; int[] tChar = new int[256]; Arrays.fill(sChar, -1); Arrays.fill(tChar, -1); for(int i = 0; i < s.length(); i++){ int sCharIdx = s.charAt(i); int stCharIdx = t.charAt(i); if (sChar[sCharIdx] == -1 && tChar[stCharIdx] == -1){ sChar[sCharIdx] = stCharIdx; tChar[stCharIdx] = sCharIdx; } else if (sChar[sCharIdx] != stCharIdx || tChar[stCharIdx] != sCharIdx) { return false; } } return true; }<p><strong>Результаты</strong></p>
20
<p><strong>Временная сложность:</strong>O(n) - так как мы перебирали все элементы массива.</p>
20
<p><strong>Временная сложность:</strong>O(n) - так как мы перебирали все элементы массива.</p>
21
<p><strong>Ёмкостная сложность:</strong>O(1) - нам нужно определённое количество места в памяти: для двух строк и для двух массивов с символами по 256 байт.</p>
21
<p><strong>Ёмкостная сложность:</strong>O(1) - нам нужно определённое количество места в памяти: для двух строк и для двух массивов с символами по 256 байт.</p>
22
<a>Научитесь: Профессия Java-разработчик + ИИ Узнать больше</a>
22
<a>Научитесь: Профессия Java-разработчик + ИИ Узнать больше</a>