Python code that will find words made out of specific letters. Any subset of the letters could be used

Question

If I have a list of words in the variable words and a list of letters in the variable letters, how can I find all the words that can be made up out of the letters in letters. Any subset of the letters in the variable letters can be used and letters can be used more than once. I would like to do this in Python.

For example:

letters = ['a', 'b', 'i', 'l', 'r', 's', 't', 'u']
words = ['dummy', 'australia']

Should return:

'australia'

even though there is an additional 'b', but not:

'dummy'

since d, m and y are not available.

Answer 1

Use regular expressions:

>>> import re
>>> m = re.compile('^[abilrstu]+$')
>>> m.match('australia') is not None
True
>>> m.match('dummy') is not None
False
>>> m.match('australian') is not None
False

Answer 2

you can use all() along with sets, because they allow O(1) membership checkup:

In [9]: words = ['dummy', 'australia']

In [10]: letters = ['a', 'b', 'i', 'l', 'r', 's', 't', 'u']

In [11]: let_set=set(letters)

In [12]: for word in words:
    if all(x in let_set for x in set(word)):
        print word
   ....:         
australia

Answer 3

This is probably the easiest way:

result = [w for w in words if all(i in letters for i in w)]

This returns ['australia']

Answer 4

This employs set intersection, which might be faster. On the other hand, it requires additional memory.

letters = ['a', 'b', 'i', 'l', 'r', 's', 't', 'u']
words = ['dummy', 'australia', 'australians' ]

f = set(letters)
c = [ (word, set(word)) for word in words ]
# changing to s & f == f makes condition "must use ALL letters"
s = [ w for (w, s) in c if s & f == s ]

s is now ['australia']

(But I'm curious about the use of such a solution. A Scrabble robot? A dusty-keyboard attack on dictionary passwords? )