Find all words that satisfy unknown letters (Hangman) I have been working on a function which might be used to solve a word game like Hangman or "Wheel of Fortune".

Basically, I wish to search from a very large WORD_LIST (>1 million unique entries) for any word which satisfies the provided letters in the word search.

An example of this might be if search is "A??LE", the resulting list will contain  apple, ankle, ...

But that technically, if a letter is already provided/revealed, then it cannot also be one of the blanks eg; search= "HANG???" might return hangout, hangers but not hangman because the A/N has already been guessed.

Mainly I'm wondering if the string search speed can be increased, or if a more elegant (RegEx?) method of searching might give me faster results without losing accuracy.

def words_like(search, without_letters='', preclude_revealed_letters=True):
    if len(search) &lt; 1:
        return []

    search = search.lower()
    without_letters = without_letters.lower()
    # Find indices of letters and blanks
    letters = [i for i, x in enumerate(list(search)) if x != "?"]
    blanks = [i for i, x in enumerate(list(search)) if x == "?"]

    if preclude_revealed_letters:
        # If a letter has been revealed, it can't also be one of the blanks
        without_letters = set(without_letters+''.join([x for x in search if x != "?"]))

    # Search our word-list for all matching "revealed" letters
    possible_words = []

    for w in WORD_LIST:
        if len(w) != len(search):
            continue
        for i in letters:
            if search[i] != w[i]:
                break
        else:
            possible_words.append(w)
    # Then remove all that use forbidden letters in the blanks
    without_possibles = []

    for w in possible_words:
        for i in blanks:
            if w[i] in without_letters:
                break
        else:
            without_possibles.append(w)
    return without_possibles
The solution would indeed be much simpler using regular expressions.  The trick is to build the regular expression dynamically, using a negated character class like [^unwanted] to represent any character other than u, n, w, a, n, t, e, or d.

I'd suggest writing this function to return a generator expression, such that it yields matching words from WORD_LIST as it finds them, rather than waiting until all of the processing is complete.

import re

def words_like(search, without_letters='', preclude_revealed_letters=True):
    forbidden_letters = set(without_letters)
    if preclude_revealed_letters:
        forbidden_letters.update(c for c in search if c != '?')
    regex = re.compile(
        search.replace('?', '[^' + ''.join(forbidden_letters) + ']'),
        re.IGNORECASE
    )
    return filter(regex.fullmatch, WORD_LIST)


This assumes that search consists only of letters and question marks, and contains no regex metacharacters such as ..

(Note that regex.fullmatch() was added in Python 3.4.  For earlier versions of Python, use regex.match, and append a $ to the regex.)