Этот пост является частью серии, в которой я буду разбирать проблемы кодирования, которые я решил, и делиться уроками, которые я усвоил, находя ответ. Языком кодирования будет JavaScript.

Добро пожаловать в мою замечательную статью с несколько подробными объяснениями процессов, которые использует мой мозг для решения задач по программированию! Они не всегда красивы, но я надеюсь, что объяснения помогут другим почесать затылок, как я, прежде чем написать это!

Эта задача очень похожа на Найти все анаграммы в строке. Отличие заключается в том, что для этой задачи Перестановка в строке мы возвращаем только логическое значение вместо массива начальных позиций.

Давайте сломаем это.

Понимание проблемы:

«Для двух строк s1 и s2 напишите функцию, которая возвращает true, если s2 содержит перестановку s1. Другими словами, одна из перестановок первой строки является подстрокой второй строки».

Мы также гарантируем 2 вещи:

Входные строки содержат только строчные буквы.

Длина обеих заданных строк находится в диапазоне [1, 10 000].

У нас есть два входа: s1 и s2. Второй вход s2 — это строка, которая должна быть длиннее, чем первый вход s1. Первый вход s1 — это подстрокаf s2. Это означает, что это непрерывная строка символов, которую можно найти в пределах s2.

Если s1 не может быть найден в пределах s2, мы возвращаем false. Если это возможно, мы возвращаем true. Нам нужно иметь дело только со строчными буквами. Достаточно легко!

Псевдокод:

  1. Вернуть false if s2 length ‹ s1 length

Если наша подстрока длиннее заданной строки, мы точно знаем, что s1 не является перестановкой нашей заданной строки.

2. Определите charCountмассив длиной 26 индексов и заполните его нулями.

Зачем нам нужен массив длиной ровно 26? Поскольку мы знаем, что имеем дело только со строчными буквами, и предполагаем, что имеем дело только с английским алфавитом: мы можем предположить, что существует не более 26 уникальных символов, которые нам нужно будет вести подсчет. Мы инициализируем каждый индекс значением 0, чтобы мы могли увеличивать/уменьшать эти значения позже.

Зачем нам нужно вести счет букв? Итак, мы знаем, сколько раз эта буква встречается в нашей подстроке s1 и сколько раз мы уже подсчитали ее в нашей строке s2. Мы хотим быть уверены, что письмо учтено, когда оно появляется в нашем окне в первый раз или когда оно покидает окно ( мы будем говорить о скользящем окне подойти позже).

3. Перебрать chars из s1 и увеличить соответствующий индекс charCount на 1 (a = 0, b = 1, c = 2, и т.д..)

Это настройка нашего начального подсчета букв в нашей подстроке s1. Мы можем использовать эти charCounts, чтобы отслеживать, где мы находимся, когда перебираем строку s2.

4. Определите левую переменную, установленную в 0, и правую переменную, установленную в 0 (используется для скользящие границы окна)

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

5. Определите переменную count со значением s1.length (используется, чтобы узнать, нашли ли мы перестановку или нет)

Когда наша переменная count равна 0, это означает, что мы успешно нашли все буквы в нашей подстроке s1 последовательно внутри нашей строки s2. Это означает, что мы вернем true сразу же, как только узнаем, что count равен 0.

6. В то время как правый цикл ‹ длины s2:

Наша переменная right является самой правой границей нашего скользящего окна. Это гарантирует, что мы дойдем до конца нашей строки s2, но не дальше.

7. если соответствующий индекс текущего символа в charCount равен ›= 1, уменьшить счетчик на 1. Обязательно увеличить право на 1 и уменьшите соответствующее значение индекса в charCount на 1

Нам придется немного поколдовать, чтобы найти соответствующий индекс для charCount текущего символа в s2. Это потребует использования метода String.charCodeAt(0) для поиска кода текущего символа в s2 и вычитания этого значения из кода символа 'а'.

Код символа 'a' равен 65. Поэтому, если мы хотим найти соответствующий индекс в charCount для нашего текущего символа в s2, мы нужно вычесть код текущего символа из 65. Если бы наш текущий символ был 'b', тогда мы бы получили 66–65 = 1. Таким образом, индекс в charCount для 'b' равно 1. Это имеет смысл, если вы составляете алфавит, начиная с индекса 0 (a = 0, b = 1, c = 2, d = 3, e = 4 и т. д.). ).

8. — if count === 0, вернуть true (найдена перестановка)

9. — if right -left === s1 length AND текущее значение индекса символов в charCount равно ›= 0, увеличьте count на 1. Обязательно увеличьте left на 1 и увеличьте текущий char в charCount на 1 (передвигая окно за пределы текущий первый индекс к следующему и возвращает наш charCount к тому, что было)

Этот шаг помогает нам перемещать левую часть нашего окна. Вычитание вправо-влево гарантирует, что наше окно не станет больше, чем длина нашей подстроки s1.

Здесь происходит одна действительно важная вещь — проверка ≥ 0 для значения в charCount[s2.charAt(left).charCodeAt(0) -"a". charCodeAt(0)]. Мы не хотим увеличивать count, если это значение еще не учтено нашей предыдущей проверкой в ​​правой части окна. Если бы значение здесь было равно -1, мы не хотели бы увеличивать нашу переменную count на 1, так как это отбросило бы оставшуюся часть нашего алгоритма (мы бы никогда не нашли перестановку если бы он существовал на самом деле). Проверяя, что значение здесь больше или равно 0, мы гарантируем увеличение count только на значения, которые когда-то были уменьшены из нашего count. strong> в правой части окна (эти значения покидают пространство окна, поэтому мы должны добавить их обратно в наш счетчик, чтобы не возвращать ложноположительный результат). ).

10. По умолчанию возвращается false (если перестановки не найдены).

Этот вызов довольно сложно объяснить. Надеюсь, просмотр окончательного кода в сочетании с этим объяснением даст вам некоторое представление. Я рекомендую добавить несколько console.log() и сломать/исправить код, пока вы не поймете, как он работает.

Код:

Замечательная особенность подхода со скользящим окном заключается в том, что время выполнения алгоритма в наихудшем случае составляет O (n). Поскольку мы всегда используем ровно 26 индексов в нашем массиве, мы получаем постоянную пространственную сложность O (1).

Вот и все!

Если у вас есть какие-либо другие решения этой проблемы или какие-либо советы для меня, дайте мне знать.