用另一组字母检查单词中字母的java算法和数据结构
我有一本20万字的字典和一组字母。我需要一个算法来检查一个单词的所有字母是否都在这组字母中。一个字一个字核对起来很慢。因为有大量的单词需要处理,所以我需要一个数据结构来处理。有什么想法吗?谢谢
例如:我有一组字母{b,g,e,f,t,u,I,t,g,n,c,m,m,w,c,s},我想检查单词“big”和“buff”。“big”的所有字母都是原始集合的子集,那么“big”就是我想要的,而“buff”不是我想要的,因为原始集合中只有一个“f”。 这就是我想做的
# 1 楼答案
可以使用数组来标记字母集。数组中的每个元素代表一个字母。要将字母转换为元素位置,只需减去ASCII码“a”或“a”。第一个元素代表“a”,第二个元素代表“b”,依此类推。那么第27个是“A”。元素值表示引用。例如,数组{2,0,1,0,…}表示类似{a,c,a}。伪代码可以是:
# 2 楼答案
对集合进行排序,然后对每个单词进行排序,并执行类似“合并”的操作
# 3 楼答案
这是拼字游戏或拼字游戏,对吗?嗯,你要做的是通过对每个单词中的字母进行排序来预先生成字典。所以,
word
变成了dorw
。然后将所有这些数据放入Trie数据结构中。因此,在Trie中,序列dorw
将指向值word
[请注意,因为我们对单词进行了排序,它们失去了唯一性,因此一个排序的单词可以指向多个不同的单词。ie您的Trie需要在其数据节点上存储一个列表或数组]
如果以后需要快速加载此结构,而无需执行所有排序步骤,则可以保存此结构
然后你要做的就是把你输入的字母也分类。然后开始递归地遍历Trie。如果当前字母与Trie中的现有路径匹配,则遵循该路径。因为可以有未使用的字母,所以也可以删除当前字母
就这么简单。每当您在Trie中遇到一个具有值的节点时,您都可以用过去到达该节点的字母来生成该词。您只需在找到这些单词时将其添加到列表中,当递归完成时,您就找到了所有可能的单词
如果您的输入中有重复的字母,您可能需要额外的逻辑来防止给定同一单词的多个实例(除非您需要)。在“省略”一个字母(只需跳过所有重复的字母)到下一个字母的步骤中,可以调用该逻辑
[编辑]您似乎想做相反的事情。我上面的解决方案找到了所有可能由一组字母组成的单词。但是你想测试一个特定的单词,看看它是否被允许,因为你有一组字母
这很简单
将可用字母存储为柱状图。也就是说,对于每个字母,您存储您拥有的数字。然后,你遍历测试单词中的每一个字母,边走边构建一个新的直方图。一旦你的一个柱状图存储桶超过了你可用字母中的值,这个单词就无法生成。如果你一直走到最后,你就能成功地创造这个词