获取作为所有子串(拼字游戏)的字谜的所有单词的列表的算法? [英] Algorithm to get a list of all words that are anagrams of all substrings (scrabble)?

问题描述

例如，如果输入字符串是 helloworld 我希望输出是这样的:

做他我们低的地狱抓住卷好单词你好降低世界...

一直到最长的单词，它是 helloworld 子字符串的字谜.例如在拼字游戏中.输入字符串可以是任意长度，但很少超过 16 个字符.

我已经进行了搜索并提出了类似特里树的结构，但我仍然不确定如何实际执行此操作.

解决方案

用于保存有效条目字典的结构将对效率产生巨大影响.将它组织成一棵树，根是单数零字母单词"，空字符串.根的每个子节点是一个可能单词的第一个字母，那些子节点是一个可能单词的第二个字母，依此类推，每个节点都被标记为它是否真的形成了一个单词.

您的测试器函数将是递归的.它以零个字母开头，从有效条目树中发现 "" 不是一个单词，但它确实有孩子，所以你递归地调用你的测试器，并用你的起始词(没有字母)附加每个可用的剩余字母输入字符串(当时是所有这些).检查树中的每个单字母条目，如果有效则做笔记；如果是儿童，则调用 tester 函数附加每个剩余的可用字母，依此类推.

例如，如果您的输入字符串是helloworld"，您将首先使用"调用您的递归测试器函数，将剩余的可用字母helloworld"作为第二个参数传递.函数看到 "" 不是一个词，但子 "h" 确实存在.所以它用h"和elloworld"来称呼自己.函数看到h"不是一个词，但子e"存在.所以它用he"和lloworld"来称呼自己.函数看到标记了e"，所以he"是一个词，注意.此外，孩子l"存在，所以下一个调用是hel"和loworld".接下来它会找到hell"，然后是hello"，然后将不得不退出并可能接下来找到hollow"，然后再次返回到空字符串，然后从e"字开始.

Eg if input string is helloworld I want the output to be like:

do
he
we
low
hell
hold
roll
well
word
hello
lower
world
...

all the way up to the longest word that is an anagram of a substring of helloworld. Like in Scrabble for example. The input string can be any length, but rarely more than 16 chars.

I've done a search and come up with structures like a trie, but I am still unsure of how to actually do this.

解决方案

The structure used to hold your dictionary of valid entries will have a huge impact on efficiency. Organize it as a tree, root being the singular zero letter "word", the empty string. Each child of root is a single first letter of a possible word, children of those being the second letter of a possible word, etc., with each node marked as to whether it actually forms a word or not.

Your tester function will be recursive. It starts with zero letters, finds from the tree of valid entries that "" isn't a word but it does have children, so you call your tester recursively with your start word (of no letters) appended with each available remaining letter from your input string (which is all of them at that point). Check each one-letter entry in tree, if valid make note; if children, re-call tester function appending each of remaining available letters, and so on.

So for example, if your input string is "helloworld", you're going to first call your recursive tester function with "", passing the remaining available letters "helloworld" as a 2nd parameter. Function sees that "" isn't a word, but child "h" does exist. So it calls itself with "h", and "elloworld". Function sees that "h" isn't a word, but child "e" exists. So it calls itself with "he" and "lloworld". Function sees that "e" is marked, so "he" is a word, take note. Further, child "l" exists, so next call is "hel" with "loworld". It will next find "hell", then "hello", then will have to back out and probably next find "hollow", before backing all the way out to the empty string again and then starting with "e" words next.

这篇关于获取作为所有子串(拼字游戏)的字谜的所有单词的列表的算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！