Возвращает bool, если строка разделяет все символы с другой строкой, включая удваивает Python-3.x - PullRequest
Новая
       6

Возвращает bool, если строка разделяет все символы с другой строкой, включая удваивает Python-3.x

0 голосов
/ 01 ноября 2018

Извините, если была задана похожая проблема, я не смог ее найти.

Мне нужно проверить, содержит ли string_a все символы из string_b, включая неуникальные.

Пример 1: 

... string_a = 'baba'
... string_b = 'baaa'
... <solution here>
False

Пример 2 (возвращает True, потому что теперь string_a имеет достаточно 'a' с): 

... string_a = 'ababa'
... string_b = 'baaa'
... <solution here>
True

Я попробовал метод set(), но он работает только в том случае, если символы строк уникальны. Итак, у меня есть это: 

... string_a = 'baba'
... string_b = 'baaa'
... return set(string_b) <= set(string_a)
True

Я хочу, чтобы оно было False, потому что string_b имеет три 'a' с и string_a только два.

Ответы [ 2 ]

0 голосов
/ 01 ноября 2018

Использование Counter в качестве решения кажется мне лучшим.

Сначала посчитайте все символы в string_a, затем пройдитесь по string_b char по char и вычтите из счетчика или завершите с ошибкой, если counter = 0. Это позволяет нам получить решение в O (n), читая каждую строку один раз. 

from collections import Counter

def is_subset(string_a, string_b):
  count = Counter(string_a)
  for c in string_b:
    if count[c] == 0:
      return False
    count[c] -= 1
  return True


print(is_subset('baba', 'baaa')) # =>False
print(is_subset('ababa', 'baaa')) # =>True
print(is_subset('aabb', 'd')) # =>False
print(is_subset('aabb', 'bbb')) # =>False
0 голосов
/ 01 ноября 2018

То, что вы делаете, интерпретирует строки как мультимножества и проверяет, является ли одно подмножеством другого. Многосетевое представление Python: collections.Counter: 

>>> from collections import Counter
>>> Counter('baba')
Counter({'b': 2, 'a': 2})
>>> Counter('baaa')
Counter({'a': 3, 'b': 1})

К сожалению, Counter не реализует метод is_subset, поэтому мы должны написать свой собственный. Вот два способа сделать это: 

def is_sub_multiset(haystack, needle):
    haystack = Counter(haystack)
    needle = Counter(needle)

    return not needle - haystack
    # OR
    # return all(haystack[elem] >= count for elem, count in needle.items())

>>> is_sub_multiset('baba', 'baaa')
False
>>> is_sub_multiset('ababa', 'baaa')
True
...