Как определить, состоит ли строка только из букв, заданных второй строкой

Question

У меня есть две строки. Как я могу определить, состоит ли первая строка только из букв, заданных второй строкой?

Например:

A = abcd
B = abbcc

должен возвращать false, поскольку d отсутствует во второй строке.

A = aab
B = ab

должен вернуть true.

Если программа в большинстве случаев возвращает false, как я могу оптимизировать эту программу? Если в большинстве случаев он возвращает значение true, как я могу его оптимизировать?

Answer 1

Сортировка обеих строк. Затем пройдитесь по A и получите указатель, проходящий через B. Если символ в A совпадает с тем, на который указывает указатель B, продолжайте смотреть через A. Если символ в A находится позже в алфавите, чем тот, на который указывает указатель B , чтобы продвинуть указатель B. Если символ в A находится в алфавите раньше, чем указывает указатель B, вернуть false. Если у вас кончилось A, верните true.

Answer 2

[Как мне] определить [если] первая строка [состоит из символов, которые появляются во] второй строке?

Вот быстрый алгоритм:

1. Обрабатывать первую и вторую строки как два набора символов S и T.
2. Выполните установленную разницу S - T. Назовите результат U.

Если U не пусто, вернуть false. В противном случае верните true.

Answer 3

Вот один простой способ.

def isComposedOf(A, B):
    bset = set(B)
    for c in A:
        if c not in bset:
            return False
    return True

Этот алгоритм обходит каждую строку один раз, поэтому он выполняется за O (len (A) + len (B)).

Когда ответ положительный, вы не можете сделать сравнение лучше чем len (A) даже в лучшем случае, потому что независимо от того, что вы должны проверять каждую букву. И в худшем случае один из символов в A скрыт очень глубоко в B. Поэтому O (len (A) + len (B)) является оптимальным с точки зрения производительности в худшем случае.

Точно так же: когда ответ «нет», вы не можете сделать лучше, чем len (B) сравнения даже в лучшем случае; и в худшем случае символ, которого нет в B, очень глубоко спрятан в A. Поэтому O (len (A) + len (B)) снова оптимально.

Вы можете уменьшить постоянный коэффициент, используя лучшую структуру данных для bset.

Вы можете избежать сканирования всего B в некоторых (не наихудших) случаях, когда ответ положительный, создавая его лениво, сканируя все больше B каждый раз, когда вы обнаруживаете в A символ, которого вы раньше не видели. *

Answer 4

> Если программа всегда возвращает false, как оптимизировать эту программу?

return false

> Если всегда возвращать true, как его оптимизировать?

return true

РЕДАКТИРОВАТЬ: Серьезно, это хороший вопрос, какой алгоритм оптимизирует в случае сбоя, и какой алгоритм оптимизирует в случае успеха. Я не знаю, какой алгоритм использует strstr, это может быть в целом хороший алгоритм, который не оптимален ни для одного из этих предположений.

Может быть, вы поймаете кого-то здесь, кто знает, не по себе. Если нет, это выглядит как хорошее место для начала чтения: Точные алгоритмы совпадения строк

Answer 5

при условии, что в строках есть все строчные буквы, тогда вы можете иметь битовый вектор и устанавливать бит на основе позиции position = str1[i] - 'a'. чтобы установить его, вы должны сделать
bitVector |= (1<<pos). А затем для str2 вы должны проверить, установлен ли бит в bitVector для всех битов, если это так, вернуть true, иначе вернуть false.