Shulou(Shulou.com)06/02 Report--

This article introduces the relevant knowledge of "how to use Python to complete the word hunting game". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Word hunt is a common game that gives you a list of letters and asks you to look for as many words as possible in those letters. There are different variants of these games, one is that you can reuse these letters multiple times (this kind of game is called hunting words), or you can only use each letter once (this kind of game is called alphabet reorganization). The longer the words in your group, the higher the score, and you can get the highest score by using all the letters.

Such games are "easy" for computers to complete, and emphasize a very useful data structure called "Trie".

Solution strategy

Let's first come up with a word "MAINE".

The first decision to be made is how we should deal with the problem. If the problem is alphabetical reorganization, then we can try all possible letter combinations and see if they are words. This is a good solution for letter reorganization, but it doesn't help us much for hunting words, because letters can be reused. So when you may find the word "name", you will never find the word "nine" again. Obviously we can't try to exhaust all possible combinations of these letters, because we don't know how many times a word can be repeated. For this reason, we step back to search a dictionary to see if the word can be made up of only the letters we have. When you have a large dictionary, this can take a lot of time, and you have to repeat this step every time you change a word.

Instead, we need a way to search for a dictionary that can quickly tell us whether a word is in the dictionary or not. This is the opportunity to use the predictive text structure Trie dictionary tree.

What is Trie?

Trie is a tree data structure-instead of the original tree node storing a value associated with key-this node now stores the key itself. The values in the node can be used to assign order to some leaf nodes or probability values according to the number of iterations.

An example of Trie in Wikipedia:

The above example of Trie is generated by "A", "to", "tea", "ted", "ten", "I", "in" and "inn". Once a Trie dictionary tree structure like this is generated, it is O (n) complexity to determine whether any word is in the Trie dictionary tree. If I was searching for "ted", I would consume O (1) to find "t", then O (1) from the "t" node to find "e", and then O (1) from the "te" node to "d".

Face the question "is this pile of letters in this dictionary?" This is a "very" quick solution. The first thing we need to do is to build a dictionary.

In Python, this step is simple. Each node should look like a dictionary. So we need to start with an empty dictionary, and then check each word in the dictionary letter by letter to see if the next letter is in our Trie dictionary tree structure, and if not, add it. Now, this sounds time-consuming, and in some ways it is, but it only needs to be done once. When Trie is built, you can use it directly without any other overhead.

Create a Trie dictionary tree

We need to start with a list full of all possible words (there are many such resources online), and then our dictionary load function might look like this:

Def load ():

With open ('words.txt') as wordFile:

WordList = wordFile.read () .split ()

Trie = {}

For word in wordList:

AddWordToTrie (trie, word)

Return trie

We need a function to add words to Trie. We skim through Trie to check each letter to see if we need to add a new key. Because we use key to retrieve dictionaries in python, there is no need to store a value on each node. This is a new dictionary with its own key value.

Def addWordToTrie (trie, word, idx = 0):

If idx > = len (word):

Return

If word [idx] not in d:

D [word [IDX]] = {}

AddWordToTrie (d [word [IDX]], word, idx+1)

Here's a simple idea. The parameter we receive is the Trie dictionary tree at the current location (note that in this example, all nodes in Trie are also a Trie), the word, and the index of the letters we are looking at in the word.

If the index exceeds the length of the word, we stop! If not, we need to check to see if the letter is already in the Trie. If the letter is not in the lower layer of the Trie, then we add a new dictionary at this level, and the current letter is the key of the dictionary. Then we call this function recursively and pass in the dictionary for our current letter (that is, Trie), the word, and the next index location.

Using these two functions, we build the Trie dictionary tree shown above. But there is a problem ahead of us. How do we know that what we find is a "word" instead of the first "part" of a real word? For example, in the Trie example above, we want "in" to return a word like "inn", but we do not want to return "te" as a word in a dictionary.

To do this, when we complete a word, "must" store a value in this node. Looking back at our addWordToTrie function, if this node represents a complete word, set the key of "leaf" to "True".

Def addWordToTrie (d, word, idx):

If idx > = len (word):

D ['leaf'] = True

Return

If word [idx] not in d:

D [word [IDX]] = {'leaf':False}

AddWordToTrie (d [word [IDX]], word, idx+1)

Now, whenever we complete a word, we set the "leaf" value of the current dictionary node to True, or we add a new node whose "leaf" value is "False".

When we load this function initialization, it should be the same setting {'leaf':False}, so we no longer need to take an empty string as the return of a valid word.

okay! We have created our Trie structure and when are we going to use it next?

Word test

Find a way to try: start with an empty list. For each letter in our word, check our Trie dictionary tree to see if it is in it. If so, get the dictionary subtree and start all over again (so we can check for duplicate letters). Keep doing this until we find a node with the leaf flag bit true, or we can't find any letters in the word in the dictionary subtree below. If we find a node labeled leaf, add the word to the list. If we don't find the next dictionary subtree, go back and execute the next letter.

Def findWords (trie, word, currentWord):

MyWords = []

For letter in word:

If letter in trie:

NewWord = currentWord + letter

If (trie [letter] ['leaf']):

MyWords.append (newWord)

MyWords.extend (findWords (trie [letter], word, newWord))

Return myWords

Note here that we are building a new word to pass to the list, but we will also recursively look for new words to expand our list.

Some readers may have discovered the next problem. What if the letters are repeated? For example, our word is "TEEN", and we are now on the "TE" node, and we have checked "t" on the subtree, which is good, and then we check "e" on the subtree and find that "tee" is a word. We add "tee" to the list. But the next letter of the word is "e" again, so we find "tee" again. There are some ways to solve this problem, but one of the easiest ways is to replace lists with collections.

Def findWords (trie, word, currentWord):

MyWords = set ()

For letter in word:

If letter in trie:

NewWord = currentWord + letter

If trie [letter] ['leaf']:

MyWords.add (newWord)

MyWords = myWords.union (findWords (trie [letter], word, newWord))

Return myWords

Now no matter how many times we find the same word, we can guarantee the uniqueness in the list. We can also de-emphasize the letters in the input words, thus saving processing time.

That's all! Using these three functions, we can find all the words that may be in the dictionary through the letters we enter. Let's package these into a main function and then give an input, and we've already done the steps.

Def main ():

Print ('Loading dictionary...')

WordTrie = load ()

Print ('Done\ n')

Word = raw_input ("What letters should we use:")

MinLength = int (raw_input ("What is the minimum word length:"))

Print ("")

Count = 0

For word in sorted (findWords (wordTrie, word, "")):

If len (word) > = minLength:

Count = count+1

Print (word)

Print (str (count) + "words found.")

Because we are not reassembling words, we have found too many words. Using the example "MAINE" mentioned above and a dictionary I found-about 370000 words-to this extent, 208 words were found. That's why I added the shortest word length. If the word length is limited to at least seven, we can get the following results:

Loading dictionary...

Done

What letters should we use: maine

What is the minimum word length: 7

Amninia

Anaemia

Anamnia

Animine

Emmenia

Enamine

Manienie

Mannaia

Meminna

Miminae

Minaean

11 words found.

It took about half a second to load the dictionary, and the subsequent search words basically felt no obvious time consumption.

It's inefficient to rebuild a tree every time for one word, so it's best to reuse it, either saving the entire data structure or trying to find more than one word at a time.

Summary

I hope this article can provide you with a basic introduction to Trie, so that you can solve some word problems. Trie is a useful data structure when you want tasks that are automatically replenished. Text messages, searches and even directions can be used to build Trie using the data in the system to help predict what users want to type next. As we can see, it is also a good structure when searching for a large number of existing paths, which in this case is a valid word.

"how to use Python to complete the word hunting game" content is introduced here, thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.