если не использовать какие-то функции сторонних библиотек, я бы сделал бы так:
из второй строки сформировал бы словарь, где подсчитал бы кол-во каждого символа
db = {}
for letter in text_src:
db[letter] = db.get(letter, 0) + 1
это должно занять O(n) + O(nlog(n)) = O(nlog(n))
времени
пройтись символами первой строки по словарю уменьшая кол-во символов и если их станет меньше 0, то все - строка не складывается
for letter in text_dst:
if db[letter] == 0:
return False
else:
db[letter] -= 1
return True
тут время тоже O(nlog(n))
Но можно решить задачу строго за линейное время O(n)
- для этого не нужно использовать словарь, и надо использовать таблицу символов, тогда поиск нужного символа занимает O(1)
, т.е. максимально быстро
def check(text_dst, text_src):
# сформировать таблицу кол-ва символов
db = [0] * 256
for letter in text_src:
db[ord(letter)] += 1
# проверить символы слова по таблице
for letter in text_dst:
index = ord(letter)
if db[index] == 0:
return False
db[index] -= 1
return True
search('a', 'aa')
выдастFalse
, это правильно? Хорошо бы написать в вопросе о лишних символах во второй строке.