Эффективно проверьте, содержит ли одна строка весь символ другого

Question

У меня есть две строки: одно слово и одно скремблирование букв. Я хочу посмотреть, хватит ли этого письма буквами для написания слова. Я придумал алгоритм для этого, но он недостаточно эффективен, и я надеялся, что смогу получить некоторую помощь, чтобы сделать это быстрее.

Вот что я до сих пор:

s1 = 'hypochondriac' 
s2 = 'yqhpwoewnqlchpijcdrxpoa' 

temp = list(s1) 
for X in s2: 
    for Y in temp: 
     if X == Y: 
      temp.remove(X) 
      X = '@' 
if temp == []: 
    print('Found ', s1) 

У меня есть вопрос, где когда-то X соответствует мне нужно увеличивать X, но я не знаю, как так что я просто взять его из уравнения, сделав его символ. Я попытался использовать break, но он не достигает достаточно большого расстояния, чтобы разбить его на петлю s2. В любом случае, я уверен, что эта двойная идея цикла слишком медленная по сравнению с тем, что будет использовать кто-то с некоторым опытом. Есть идеи?

Answer 1

Ваш код не эффективен, нет, потому что вы итерации в двойном цикле. Для каждой буквы в s1 в наихудшем сценарии (без совпадений) вы перебираете все из s2.

Вместо этого используйте Counter object; они действуют как несколько наборов, где вы можете как тест, если символ присутствует в O (1) время и управлять остальными пунктами:

from collections import Counter 

def contains(s1, s2): 
    s2set = Counter(s2) 
    for c in s1: 
     count = s2set[c] 
     if not c: 
      return False 
     if count == 1: 
      del s2set[c] 
     else: 
      s2set[c] = count - 1 
    return True 

Вы также можете превратить s1 в многопрофильный набор и проверки если мульти-набор для s2 содержит достаточное количество букв для каждой записи:

def contains(s1, s2): 
    s1set = Counter(s1) 
    s2set = Counter(s2) 
    for c, count in s1set.items(): 
     if count > s2set[c]: 
      return False 
    return True 

последний может быть уменьшен с all() function, который возвращает False раньше, если какой-либо из результатов он передается в False, True в противном ISE:

def contains(s1, s2): 
    s2set = Counter(s2) 
    return all(count <= s2set[c] for c, count in Counter(s1).items()) 

Во всех этих вы только перебрать как s1 и s2раз (либо непосредственно, либо для получения мульти-набор).

Демонстрация последнего:

>>> from collections import Counter 
>>> def contains(s1, s2): 
...  s2set = Counter(s2) 
...  return all(count <= s2set[c] for c, count in Counter(s1).items()) 
... 
>>> s1 = 'hypochondriac' 
>>> s2 = 'yqhpwoewnqlchpijcdrxpoa' 
>>> contains(s1, s2) 
True 
>>> contains(s1 + 'b', s2) 
False 

Answer 2

ли это наоборот. Удалить символы из s2:

s1 = 'hypochondriac' 
s2 = 'yqhpwoewnqlchpijcdrxpoa' 

temp = list(s2) 
try: 
    for ch in s1: 
     temp.remove(ch) 
except ValueError: 
    print("not found") 
else: 
    print("found", s1) 

Answer 3

Расширение @Martijn_Pieters решение, которое вы можете использовать Counter таким образом:

from collection import Counter 
def contains(s1, s2): 
    c1, c2 = Counter(s1), Counter(s2) 
    return all(c1[c] <= c2[c] for c in s1) 

Вы можете рассчитывать на то, Counter[key] будет по умолчанию возвращения 0 если key не существует ,

Answer 4

или подойти к проблеме с другого путем

s1 = 'hypochondriac' 
s2 = 'yqhpwoewnqlchpijcdrxpoa' 


for i in s1: 
    if not i in s2: 
     print 'not found' 

Answer 5

Вот Векторизованный подход с использованием NumPy -

import numpy as np 

def in_string(s1,s2): 
    arr1 = np.fromstring(s1, dtype=np.uint8) 
    arr2 = np.fromstring(s2, dtype=np.uint8) 
    return np.in1d(arr1,arr2).all() 

Пример запуск -

In [50]: in_string('hypochondriac','yqhpwoewnqlchpijcdrxpoa') 
Out[50]: True 

# Let's add in a `z` at the end of first word which isn't in the scramble 
In [51]: in_string('hypochondriacz','yqhpwoewnqlchpijcdrxpoa') 
Out[51]: False 

---

Вот еще Нампы у на основе один с использованием np.searchsorted -

def in_string_v2(s1,s2): 
    arr1 = np.fromstring(s1, dtype=np.uint8) 
    arr2 = np.fromstring(s2, dtype=np.uint8) 
    u1 = np.unique(arr1) 
    u2 = np.unique(arr2) 
    return ~(np.searchsorted(u2,u1) == np.searchsorted(u2,u1,'right')).any() 

---

Вот еще один, который обрабатывает список слов за один раз против одного карабкаются в то время -

def in_string_v3(list_s1,s2): 
    l_arr1 = np.fromstring("".join(list_s1), dtype=np.uint8) 
    arr2 = np.fromstring(s2, dtype=np.uint8) 
    lens = np.array(map(len,list_s1)) 
    comp_lens = np.in1d(l_arr1,arr2).cumsum()[lens.cumsum()-1] 
    calc_lens = np.append(comp_lens[0],comp_lens[1:]-comp_lens[:-1]) 
    return lens == calc_lens 

Пример выполнения -

In [185]: ls1 = ['hypochondriac','hypochondriachsdhsahdsadhsa','hihfheifheozz'] 

In [186]: s2 = 'yqhpwoewnqlchpijcdrxpoadjksdgdkjsfkbdsfbdsdsaduiawyei' 

In [187]: in_string_v3(ls1,s2) 
Out[187]: array([ True, True, False], dtype=bool) 

Еще один способ обработки списка слов по-другому -

def in_string_v4(list_s1,s2): 
    l_arr1 = np.fromstring("".join(list_s1), dtype=np.uint8) 
    arr2 = np.fromstring(s2, dtype=np.uint8) 
    lens = np.array(map(len,list_s1)) 
    clens = lens.cumsum() 
    non_matching_idx = np.nonzero(~np.in1d(l_arr1,arr2))[0] 
    non_matching_grp = np.unique(clens.searchsorted(non_matching_idx)) 
    return ~np.in1d(np.arange(len(list_s1)),non_matching_grp)