Как проверить, является ли одна строка подпоследовательностью другого?

Автор оригинала: Shubham Sayon.

🏢 Компании, которые задавали эту проблему: Accolite, Tesco, Google

Постановка проблемы

Описание

Учитывая две строки str1 и str2 , проверьте, если str1 это подпоследовательность str2 Отказ

А подпоследовательность строки – это новая строка, которая формируется из исходной строки, удаляя некоторые (может быть ни одного) символов, не нарушая относительные позиции оставшихся символов. (I.e., «Туз» – это подпоследовательность «ABCDE» в то время как «AEC» не).

Ограничения :

• 0 волн
• 0 волн ⁴
• str1 и str2 состоят только в строчных английских буквах.

Пример

Input: str1 = "abc", str2 = "ahbgdc"
Output: True

Input: str1 = "axc", str2 = "ahbgdc"
Output: False

Пограничные случаи

• Если str1 и str2 Оба пустые, затем выходные → Правда , как пустая строка подпоследовательность другой пустой строки.
• Если str1 → Пусто и str2 → Не пусто, то вывод → Правда Как пустая строка также является подпоследовательностью любой данной строки.
• Если str1 → Не пусто и str2 → Пусто, затем вывод → Ложь , как не пустая строка не может быть подпоследовательностью пустой строки.

Input: str1 = "", str2 = ""
Output: True

Input: str1 = "", str2 = "ahbgdc"
Output: True

Input: str1 = "abc", str2 = ""
Output: False

Предлагаемый обзор решений

Пройти через каждый символ в данных строках. Есть два случая, когда вы делаете это:

1. Текущие символы обеих строк равны. Итак, перейдите к следующему следующему индексу/символу str1 и str2 Отказ
2. Текущие символы обеих строк не равны. Итак, перейдите к следующему индексу/символу str2 Отказ Однако индекс str1 Остается фиксированным в этом случае, поскольку соответствующий персонаж не найден.

Вышеуказанный процесс повторяется до тех пор, пока не выполнены один из следующих критериев:

1. Все персонажи str1 найдены, чтобы присутствовать в str2 Отказ Длина str1 и текущее значение index_str1 будет равным в этом случае. Это обозначает, что мы успешно нашли подпоследовательность в данной строке. Другими словами, str1 является подпоследовательностью str2 Отказ
2. Все персонажи str2 были пройдены. Это означает, что либо последний символ str1 и str2 равны или str2 не подпоследовательность str1 Отказ

Диаграмматическое представление:

Решение

def isSubSequence(str1, str2):
    len_str1 = len(str1)
    len_str2 = len(str2)
    index_str1 = 0  
    index_str2 = 0  
    # Traverse both str1 and str2
    while index_str1 < len_str1 and index_str2 < len_str2:
        # Compare current character of str2 with str1
        if str1[index_str1] == str2[index_str2]:
            # If matched, then move to next character in str1
            index_str1 = index_str1 + 1
        index_str2 = index_str2 + 1
    return index_str1 == len_str1


val_1 = 'abc'
val_2 = 'ahbgdc'
print(isSubSequence(val_1, val_2))

Выход:

True

Пояснение кода:

• len_str1 и Len_str2 Хранить длину str1 и str2 соответственно.
• index_str1 и index_str2 используются для хранения показателей каждого персонажа str1 и str2 соответственно.

• в то время как Цикл используется для прохождения сквозь строки до тех пор, пока совпадение не найдена или все индексы STR2 были пройдены в случае отсутствия совпадения.

  • Если заявление сравнивает текущий символ str1 и str2 Отказ

    • Если совпадение найдено, индекс следующего символа в str1 учитывается.
  • Значение index_str1 увеличивается на каждой итерации, чтобы пройти через все доступные буквы в str1 до тех пор, пока подпоследовательность найден.
• Наконец, если подпоследовательность Был найден ценность, хранящаяся index_str1 будет равен длине str1 Отказ

Пробный прогон:

В следующей таблице иллюстрирует операцию на каждой итерации в цикле пока не найдено.

📹 Видео-решение

Я профессиональный Python Blogger и Content Creator. Я опубликовал многочисленные статьи и создал курсы в течение определенного периода времени. В настоящее время я работаю полный рабочий день, и у меня есть опыт в областях, таких как Python, AWS, DevOps и Networking.

Вы можете связаться со мной @:

• Заработка
• Linkedin.