Return bool if a string shares all characters with another string including doubles Python-3.x

user_10431088 0
Viewed 67

I'm sorry if a similar problem has been asked, I could not find it.

I need to check whether string_a contains all the characters from string_b including the non-unique ones.

Example 1:

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

Example 2 (returns True because now string_a has enough 'a's):

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

I tried set() method but it only works if the characters of the strings are unique. So I have this:

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

I want it to be False because string_b has three 'a's and string_a only two.

python-3.6 python-3.x python string
2 Answers

What you're doing is interpreting the strings as multisets and checking if one is a subset of the other. Python's multiset representation is collections.Counter:

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

Unfortunately, Counter doesn't implement a is_subset method, so we have to write our own. Here are two ways to do it:

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
user_12229510

Using Counter as a solution seems best to me.

First count all characters in string_a, then go through string_b char by char and substract from the counter or fail if counter=0. This allows us to get a solution in O(n), reading each string once.

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
user_42781160
Related