我有一个字符串和另一个包含字符串列表的文本文件。
当两个字符串按字母顺序排序后完全相同时，我们将它们称为“兄弟字符串”。
例如“abc”和“cba”会被排序为“abc”和“abc”，所以原来两者是兄弟关系。但“abc”和“aaa”则不然。
那么，有没有一种有效的方法可以根据提供的一个字符串从文本文件中挑选出所有兄弟情字符串呢？
例如，我们有"abc"和一个文本文件，其内容如下：
abc
cba
acb
lalala
then "abc", "cba", "acb"就是答案。
当然，“排序和比较”是一个很好的尝试，但“高效”是指如果有一种方法，我们可以在一次处理后确定候选字符串是否与原始字符串是兄弟关系。
我认为这是最有效的方法。毕竟，即使不阅读候选字符串，您也无法说出答案。对于排序，大多数时候，我们需要对候选字符串进行不止 1 次传递。所以，哈希表可能是一个很好的解决方案，但我不知道该选择什么哈希函数。
我能想到的最有效的算法：
- 为原始字符串设置哈希表。设每个字母为键，该字母在字符串中出现的次数为值。将此哈希表称为 inputStringTable
- 解析输入字符串，每次看到一个字符，将哈希条目的值加一
- 对于文件中的每个字符串
- 创建一个新的哈希表。称这个为兄弟StringTable。
- 对于字符串中的每个字符，将一个字符添加到新的哈希表中。如果 BrotherStringTable[character] > inputStringTable[character]，则该字符串不是兄弟（一个字符出现太多次）
- 解析字符串后，将每个 inputStringTable 值与相应的 BrotherStringTable 值进行比较。如果不同，则该串不是兄弟串。如果全部匹配，则该字符串是兄弟字符串。
这将是 O(nk)，其中n是输入字符串的长度（任何比输入字符串长的字符串都可以立即丢弃），k是文件中字符串的数量。任何基于排序的算法都将是 O(nk lg n)，因此在某些情况下，该算法比基于排序的算法更快。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
