Сложность: medium
Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.
Пример:
Input: source = "abc", target = "abcbc"
Output: 2
👨💻 Алгоритм:
1⃣Используй два указателя для отслеживания текущих позиций в строках source и target.
2⃣Перебирай символы строки source, пока не найдешь совпадающий символ в target.
Если ты прошел всю строку source и не нашел все символы target, увеличь счетчик количества подпоследовательностей и начни снова с начала source.
3⃣Повтори шаги 2 и 3 до тех пор, пока не пройдешь всю строку target.
😎 Решение:
def minSubsequences(source, target):
subsequences_count = 0
target_index = 0
while target_index < len(target):
source_index = 0
subsequences_count += 1
start_index = target_index
while source_index < len(source) and target_index < len(target):
if source[source_index] == target[target_index]:
target_index += 1
source_index += 1
if target_index == start_index:
return -1
return subsequences_count
Ставь 👍 и забирай 📚 Базу знаний