Valid Anagram | Leetcode 242 | Решение за секунды | Собеседование в Infosys, TCS, Wipro | Самый ч...

Задача Valid Anagram | Leetcode 242 встречается на собеседованиях в Infosys, TCS и Wipro, потому что она проверяет частоту встречаемости символов и временную сложность в одной небольшой задаче. В этом видео дается самое простое объяснение задачи Valid Anagram: проверка длины, массив частот из 26 символов и трюк с инкрементом минус декрементом в одном цикле. Задача Valid Anagram требует вернуть true, если строка t является анаграммой строки s, в противном случае — false. Анаграмма — это слово, образованное путем перестановки букв другого слова, используя каждую исходную букву ровно один раз. Самый простой способ — отсортировать обе строки и сравнить их, но сортировка стоит O(n log n). Более разумный способ — подсчет частоты встречаемости. Поскольку входные данные содержат только строчные английские буквы, существует ровно 26 возможных символов, поэтому мы можем использовать фиксированный массив размером 26 вместо хеш-карты. В этом видео сначала объясняется задача, а затем приводится максимально чистое решение на Java. Начнём с базового случая, о котором большинство забывает: если длина строки s не равна длине строки t, немедленно вернём false. Разные длины никогда не могут быть анаграммами, поэтому нет смысла их подсчитывать. Затем создадим целочисленный массив размером 26. Пройдёмся по обеим строкам одновременно: для каждого символа в s выполним count[s.charAt(i) минус a] плюс плюс, а для каждого символа в t — count[t.charAt(i) минус a] минус минус. Если обе строки являются анаграммами, каждое увеличение отменяется соответствующим уменьшением, и каждая ячейка заканчивается нулем. После цикла просканируем массив, и если какое-либо значение не равно нулю, вернём false, в противном случае — true. Это работает за время O(n) и занимает пространство O(1). Затем рассмотрим следующий вопрос, который так любят задавать на собеседованиях: что если входные данные содержат символы Unicode? В Unicode нет фиксированного алфавита из 26 символов, поэтому подход с массивом не работает. Решение заключается в использовании HashMap, где каждый символ в строке s равен единице, затем для каждого символа в строке t мы уменьшаем значение ключа и удаляем его, когда его значение достигает нуля. Если в конце HashMap пуст, мы возвращаем true, в противном случае — false. В заключение мы приводим полный разбор Java-кода, пример успешной отправки решения, прошедшего все тестовые случаи, и точную интуицию, которую вы можете повторить на любом собеседовании в Infosys, TCS или Wipro. Разделы (на основе реального контента SRT): 00:00 — Завязка: Почему Infosys, TCS, Wipro запрашивают корректные анаграммы 00:48 — Чтение вслух условия задачи LeetCode 242 02:05 — Что именно представляет собой анаграмма? 03:25 — Базовый случай: сначала проверяем длины 05:00 — Частотный массив размером 26 (строчные буквы английского языка) 06:40 — Увеличение s, уменьшение t, проверка нулей 08:10 — Построчный разбор кода на Java 09:45 — Отправка и прохождение всех тестовых случаев 10:25 — Дополнение: ввод в формате Unicode означает HashMap 11:30 — Заключение: код, сообщество, подписка Полный код: https://github.com/Shaanworkspace/YOU... Больше от Shaan Labs: Ежедневные решения LeetCode → https://github.com/Shaanworkspace/YOU... Часто задаваемые вопросы: Что такое допустимая анаграмма LeetCode 242? В задании LeetCode 242 требуется вернуть true, если строка t является анаграммой строки s, в противном случае — false. Анаграмма — это слово, образованное путем перестановки букв другого слова, при этом каждая исходная буква используется ровно один раз. Например, «anagram» и «nagaram» — анаграммы, а «rat» и «car» — нет. Почему на собеседованиях в Infosys, TCS и Wipro задают вопрос о валидности анаграмм? Компании, предоставляющие услуги, повторяют этот вопрос, потому что это быстрая проверка понимания кандидатом частоты символов, базового случая проверки длины и компромиссов между O(n) и O(n log n). Задание достаточно небольшое, чтобы выполнить его за короткий раунд собеседования, но достаточно содержательное, чтобы обсудить возможности оптимизации. Как проще всего решить задачу о валидности анаграмм? Сначала проверьте, что две строки имеют одинаковую длину, затем используйте массив частот размером 26. Увеличивайте счетчик для каждого символа строки s и уменьшайте для каждого символа строки t. Если в конце каждая ячейка равна нулю, строки являются анаграммами. Это выполняется за время O(n) и занимает пространство O(1). Почему мы проверяем длину строк перед подсчетом частоты? Если длины различаются, строки никогда не могут быть анаграммами, поэтому немедленное возвращение false избавляет от необходимости создавать массив частот. Пропуск этого базового случая тратит время на входные данные, которые никогда не могут совпадать, и является наиболее распространенной ошибкой, которую допускают кандидаты. Как обрабатывать последующую проверку на Unicode в Valid Anagram? Когда входные данные могут содержать символы Uni...