javascript - 如何检查字符串的排列(或部分)是否在列表(字典)中？

Question

我正在为拼字游戏编写一个简单的搜索应用程序。从一个字符串中找出所有可能的单词。排列部分完成。我创建了一个函数 Permute(string)，它输出一个包含所有排列的数组。

var dictionary=["abc","abcd",ab","dhgd","adbft"];

var input="abcd";
    output=Permute(input);
    //result:
    0:"abcd"
    1:"abdc"
    2:"acbd"
    3:"acdb"
    4:"adbc"
    5:"adcb"
...etc

现在，我必须检查单词是否存在。我应该尝试所有长度吗？还有其他更有效的方法吗？

    //Check all the item of the output array
    for(var i=0; i<output.length;i++){
        //Check if all length of output
        for(var j=2;j<output[i].length;i++)
            //Check all these possibilities if they exist in the dictionary
            for(word in dictionary){
                output[i].substring[1:j]==dictionary[word];
}

    }};

我真的无法想象，如果字典是 250 000 个单词，那会有多长...有没有更好的方法？

Answer 1

您不需要生成所有排列。取而代之的是，将您的 key 作为字母一个 排列的字典。词汇上最小的排列是最简单的——只需对键中的字母进行排序。

所以你的字典变成了一个映射，从一个排序的字母字符串到这个字符串的字谜，实际上是单词。例如，如果 'god' 和 'dog' 是单词，那么您的字典将有一个条目 'dgo' -> ['dog','god '].

然后，要进行搜索，只需对输入中的所有字母进行排序，然后检查字典以查找结果字符串的所有子序列。

如果您有 'ogdb'，排序会生成 'bdgo'，然后您检查字典中的 'b'，'d', 'g', 'o', 'bd', 'bg'、'bo' 等。当您到达'dgo' 时，您会找到'god' 和' dog' 在字典中。

7 个字母，有 127 个可能的子序列。检查 127 个键的字典非常快。