If you know how to determine if you can make a word string from the given chars characters, using each character in chars no more than its number of repetitions (the can_build(word, chars) is known as the can_build(word, chars) predicate), then the problem comes down to:
result = list(filter(can_build, lst2))
or more read:
result = [word for word in lst2 if can_build(word)]
where can_build uses chars = lst1 inside.
If it were required to use all the characters from chars , then it would be a check whether the word an anagram of chars , for example: “enlightener” can be obtained by rearranging the letters “patience” . Similar solutions can be used when exact equality is replaced with "no more".
can_build() can be implemented by finding whether a word multiset a subset of the chars multiset. If all the characters in chars and word were unique, then
can_build = set("1234").issuperset
collections.Counter implements the idea of a set in which elements can be repeated, that is, multisets . As shown in the elegant solution in the @Timofey Bondarev response , you can use this collection to implement can_build :
can_build = lambda word, chars=Counter(lst1): not (Counter(word) - chars)
You can implement the same algorithm manually without using collections.Counter .
from collections import defaultdict def Counter(letters): counts = defaultdict(int) for letter in letters: counts[letter] += 1 return counts chars_count = Counter(chars) def can_build(word): return all(chars_count[char] >= count for char, count in Counter(word).items())
You can use a simple list, if all the characters belong to an alphabet, then since the chars the same all the time, you can chars.count values. For example, if chars can contain only the numbers 0-9 :
from string import digits chars_count = [(digit, chars.count(digit)) for digit in digits] def can_build(word): return all(word.count(digit) <= count for digit, count in chars_count)
this is an O(N * M) solution ( M=len(digits) —the size of the alphabet), in contrast to the O(N) solution that uses Counter() . If the alphabet is not fixed: alphabet = set(word) , then this is an O(N**2) (quadratic) algorithm. If the alphabet fixed as in the example, then this is an O(N) (linear) solution. For a small alphabet, for example, for boolean numbers ( alphabet=(0,1) ) or DNA strings ( alphabet="GTAC" ), this solution could be even faster than solutions with Counter() .
Another application example: if word , chars are numbers represented by their simple factors (for example: (2,2,3) represents 12 , (5,7) represents 35 ), then can_build() answers the question whether the word divider chars , that is, is it true that: chars % word == 0 .
Q: how to implement the code if you get rid of the condition that the element should be repeated as many times as it is in the first list ???
Already the answer in this assumption works. Otherwise it would be an anagram case: the number of repetitions is the same. Solutions with Counter() and with <= , >= NOT require the element to be repeated "as many times as it is in the first list" (less is possible).
If you mean that the number of repetitions is not important at all, but only whether there is an element or not, then the situation is similar to the case when all elements are unique, that is:
can_build = set(lst1).issuperset
as already mentioned above.
