在填充有随机放置字符的列表中搜索单词 [英] Search for words in a list filled with randomly put characters

问题描述

我有一个问题：

如果我要列出一个字母列表，让我们用以下字母填充：

If I would have a list of letters, let's fill it with:

A

T

C

我想让算法找出根据我给出的单词列表创建哪些单词的组合（它们的长度不必与列表的长度相同）

I would want the algorithm to figure out which combinations creates words based off of a list of words I give it (they don't have to be the same length as the list's)

所以从这里开始，像这样：

So from here it would go like this:

CAT, ACT, A etc etc.

我遇到的问题是了解算法的基本原理。

What I'm having problems with is to understand how the basics of the algorithm should be.

有人知道如何帮助我开始工作吗？

Does anyone know how to help me start working on this?

推荐答案

<我认为蛮力方法是最简单的。该算法基本上是要查找字母集合的每个子集，并检查它是否在字典中。对于每个字母，它将检查是否在单词中而不是单词中。

I think a brute force approach would be simplest. The algorithm is basically going to find every subset of your set of letters and check if it is in the dictionary. For each letter, it will check the possibility that it is in the word and not in the word.

您的字典数据结构应进行排序，以便确定单词是否

Your dictionary data structure should be sorted so that whether or not a word is contained can be checked quickly using binary search (or you can use a hash set).

伪代码看起来像这样：

A = array of letters
S = empty list

IS_VALID(word, i)
    //base case: reached the end of the letters
    if i > length(A) - 1
        return

    if dictionary contains word
        add word to S

    //check for all words containing A[i]
    IS_VALID(w + A[i], i+1)
    //check for all words excluding A[i]
    IS_VALID(w, i+1);

//initialization
IS_VALID("", 0)

其中 word 是您当前正在查看的字符串，而 i 是<$ c $中字母的索引c> A 您目前正在考虑在单词的末尾附加。

where word is the string you are currently looking at and i is the index of the letter in A you are currently thinking of appending to the end of word.

这篇关于在填充有随机放置字符的列表中搜索单词的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！