Сложность: medium
Учитывая массив строк queries и строку pattern, верните булевский массив answer, где answer[i] - true, если queries[i] соответствует pattern, и false в противном случае. Слово запроса queries[i] соответствует pattern, если вы можете вставить строчные английские буквы pattern так, чтобы они были равны запросу. Вы можете вставить каждый символ в любую позицию и не можете вставить ни одного символа.
Пример:
Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]
👨💻 Алгоритм:
1⃣Инициализация переменных:
Создайте массив answer для хранения результатов соответствия каждого запроса шаблону.
2⃣Проверка каждого запроса:
Для каждого запроса из queries, проверьте, можно ли вставить строчные буквы в pattern, чтобы они соответствовали запросу.
Используйте два указателя, один для query и один для pattern. Перемещайте оба указателя, пока они не достигнут конца строк. Если текущие символы совпадают, переместите оба указателя. Если символы не совпадают и текущий символ в запросе является строчной буквой, переместите только указатель запроса.
3⃣Возврат результата:
Если указатель шаблона достиг конца строки, добавьте true в answer, иначе добавьте false.
Верните массив answer.
😎 Решение:
class Solution:
def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
def matches(query, pattern):
i, j = 0, 0
while i < len(query):
if j < len(pattern) and query[i] == pattern[j]:
j += 1
elif query[i].isupper():
return False
i += 1
return j == len(pattern)
return [matches(query, pattern) for query in queries]
Ставь 👍 и забирай 📚 Базу знаний