javascript - 在javascript中制作anagrams生成器仅查找列表中包含的单词

Question

我正在尝试用 javascript 改进这个字谜生成器:

JS:

var str,re,cnt,cntmax;

function rst(){
    cnt=0; cntmax=10000; str="";
    if (document.forms[0].re.value != ""){
        re=new RegExp(document.forms[0].re.value);
    } else { re=null; }
}

function go(prefix, postfix){
    if (cnt>=cntmax) return;
    if (postfix==""){
        if (re==null || prefix.match(re)==null){
            str+=prefix+"\r\n"; cnt++;
        }
        return;
    }
    for (var i=0;i<postfix.length;i++){
        var prefix2=prefix+postfix.charAt(i);
        var postfix2=postfix.substring(0,i)+postfix.substring(i+1);
        go(prefix2,postfix2);
    }
}

HTML:

<form>
Anagram this word:<input type="text" name="t" /> <br>
Exclude these pat:<input type="text" name="re" /> <br>
<input type="button" value="Generate anagrams (max 10000)"
onClick="javascript: rst(); go('', t.value); tout.value=str; console.log('Anagrams: '+cnt);" />
<br>
<textarea name="tout" rows=10 cols=40></textarea>
</form>

有一些问题需要修复，例如需要一个单词分隔符(如分割)来排除单词，
但最重要的是让生成器只查找列表(如数据库)中收集的单词......我不知道如何创建该列表，请帮忙...

DEMO HERE

Answer 1

根据单词列表的大小，您最好使用可以访问数据库的服务器端代码来实现此目的。但假设您确实想使用 JavaScript 客户端，我会回答您的问题。

最简单的方法是只有一个单词数组并检查每个字符串是否包含在列表中。如果您想要更好的性能，您可以对其进行预排序并使用二分搜索，但此示例将仅使用简单的线性搜索。

   var dictionary = [
     "apple",
     "banana",
     "orange",
     "pear",
     "watermelon"
   ];

   function isValidWord(word) {
     for(var i = 0, n = dictionary.length; i < n; i++) {
       if(word === dictionary[i]) {
         return true;
       }
     }
     return false;
   }

然后您可以更改此行:

   if (re==null || prefix.match(re)==null){

对此:

   if ((re==null || prefix.match(re)==null) && isValidWord(prefix) ){

现在，正如我提到的，这可能是一个非常大的字典的性能问题。想象一下你的字典有一百万个单词，而你正在寻找一个 4 个字母的单词。你得到的排列数是 24，所以需要在字典中搜索 24 次。如果在中间找到平均单词，则需要进行 1200 万次比较。哎呀!如果这对您来说是个问题，请阅读二分搜索算法。

尽管如此，如果字典很大，那么还存在需要将整个字典发送给客户端的问题。您可以使用某种 zip 算法来减少一点，但即使这样，它也可能太多了。此时，您可能需要使用服务器端字谜检查器并发回结果。

另一件事需要注意的是，您应该将字谜列表构建到一个数组中，扔掉任何坏的，然后确保删除任何重复项。您会注意到我提供的代码中“baaann”出现了大量“banana”的重复项。这是因为您创建排列的算法没有考虑重复的字母。