«Учебный план LeetCode 75 для лучших интервью» — это учебный план, который предлагает график выполнения набора из 75 задач по программированию на LeetCode в течение нескольких недель с целью подготовки навыков для технических собеседований и улучшения кодирования.

205. Изоморфные струны.

Имея две строки s и t, определить, изоморфны ли они.

Две строки s и t изоморфны, если символы в s можно заменить, чтобы получить t.

Все вхождения символа должны быть заменены другим символом с сохранением порядка символов. Никакие два символа не могут отображаться на один и тот же символ, но символ может отображаться на самого себя.

Пример 1:

Ввод: s = яйцо, t = добавить
Вывод: true

Пример 2:

Ввод: s = foo, t = bar
Вывод: false

Пример 3:

Ввод: s = paper, t = title
Вывод: true

В этой задаче нам даны две строки s и t, и нам нужно определить, изоморфны ли они. Две строки изоморфны, если мы можем получить одну строку из другой, заменив некоторые символы другими символами так, чтобы результирующие строки были идентичными.

Например, в первом примере s означает «яйцо», а t — «добавить». Если мы заменим «e» на «a» и «g» на «d», мы получим «добавить», что идентично t. Следовательно, s и t изоморфны.

С другой стороны, во втором примере s — это «foo», а t — это «bar». Если мы попытаемся заменить «f» на «b», «o» на «a», мы получим «baa». Это не идентично t, поэтому s и t не изоморфны.

Чтобы решить эту проблему, мы можем использовать сопоставление между символами s и t. Мы можем перебирать символы s и t и проверять, сопоставлены ли уже символы в каждом индексе друг с другом. Если это не так, мы можем сопоставить их и продолжить. Если они уже сопоставлены и сопоставлены неправильно, мы можем вернуть false. Если мы достигнем конца строки и все сопоставления верны, мы можем вернуть true.

Решение

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        mapping = {}
        for c1, c2 in zip(s, t):
            if c1 in mapping:
                if mapping[c1] != c2:
                    return False
            elif c2 in mapping.values():
                return False
            else:
                mapping[c1] = c2
        return True

Описание решения

В этом решении используется словарь (называемый mapping) для хранения сопоставления между символами s и t. Затем он параллельно перебирает символы s и t, используя функцию zip.

Для каждой пары символов c1 и c2 решение проверяет, есть ли уже c1 в словаре mapping. Если это так, он проверяет, равно ли значение c1 в словаре c2. Если это не так, функция возвращает False, так как это будет означать, что отображение недействительно.

Если c1 отсутствует в словаре mapping, решение проверяет, присутствует ли уже значение c2 в значениях словаря mapping. Если это так, функция возвращает False, потому что это будет означать, что c2 уже сопоставлен с каким-то другим символом в s.

Если c1 отсутствует в словаре mapping, а значение c2 отсутствует в значениях словаря mapping, решение добавляет сопоставление от c1 к c2 в словарь mapping.

Наконец, если цикл завершен и значение False не возвращено, функция возвращает True, указывая на то, что строки s и t изоморфны.

392. Является следствием

Учитывая две строки s и t, вернуть true, еслиsявляется подпоследовательностью строкиt, илиfalse иначе.

Подпоследовательность строки — это новая строка, сформированная из исходной строки путем удаления некоторых (может быть ни одного) символов без нарушения относительного положения оставшихся символов. (т. е. "ace" является подпоследовательностью "abcde", а "aec" — нет).

Пример 1:

Ввод: s = abc, t = ahbgdc
Вывод: true

Пример 2:

Ввод: s = axc, t = ahbgdc
Вывод: false

В этой задаче нам даны две строки s и t, и нам нужно определить, является ли s подпоследовательностью t. Строка s является подпоследовательностью t, если возможно получить s путем удаления некоторых (или ни одного) символов t так, чтобы относительные положения оставшихся символов сохранялись.

Например, в первом примере s — это «abc», а t — это «ahbgdc». Если мы удалим символы «h», «b» и «d» из t, у нас останется «ac», который идентичен s. Следовательно, s является подпоследовательностью t.

С другой стороны, во втором примере s — это «axc», а t — это «ahbgdc». Невозможно удалить символы из t так, чтобы результирующая строка была «axc». Следовательно, s не является подпоследовательностью t.

Чтобы решить эту проблему, мы можем пройтись по символам s и проверить, присутствует ли каждый символ в t. Если это так, мы можем удалить его из t и перейти к следующему символу. Если мы достигли конца s и все символы были найдены в t, мы можем вернуть True. В противном случае мы можем вернуть False.

Решение

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i, j = 0, 0 

        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i+=1
            j+=1
        return True if i == len(s) else False

Описание решения

Это решение перебирает символы s и t параллельно, используя две переменные i и j в качестве индексов. Он начинается с i=0 и j=0 и увеличивает j, пока не найдет символ в t, который соответствует текущему символу в s. Когда он находит совпадение, он увеличивает i, чтобы перейти к следующему символу в s.

Цикл продолжается до тех пор, пока либо i не станет равным длине s, либо j не станет равным длине t. Если i становится равным длине s, это означает, что все символы s были найдены в t и функция возвращает True. В противном случае, если j становится равным длине t, это означает, что не все символы s были найдены в t и функция возвращает False.

Это решение работает, потому что оно проверяет символы s в том порядке, в котором они появляются, и останавливается, как только находит символ, которого нет в t. Это гарантирует сохранение относительного положения символов.