我试图使用itertools.permutations()返回字符串的所有置换,并且只返回属于一组单词的成员的置换。
import itertools
def permutations_in_dict(string, words):
'''
Parameters
----------
string : {str}
words : {set}
Returns
-------
list : {list} of {str}
Example
-------
>>> permutations_in_dict('act', {'cat', 'rat', 'dog', 'act'})
['act', 'cat']
'''
我目前的解决方案在终端上运行良好,但不知何故无法通过测试用例。。。
return list(set([''.join(p) for p in itertools.permutations(string)]) & words)
任何帮助都将不胜感激。
问题类别
您解决的问题最好描述为测试anagram匹配。
使用排序的解决方案
traditional solution是对目标字符串进行排序,对候选字符串进行排序,并测试是否相等。
使用多集的解决方案
另一种方法是使用collections.Counter()进行multiset相等测试。这在算法上优于排序解决方案(
O(n)
与O(n log n)
),但往往会丢失,除非字符串的大小很大(由于散列所有字符的成本)。使用完美散列的解决方案
唯一的anagram签名或perfect hash可以通过乘以与字符串中每个可能的字符对应的素数来构造。
commutative property of multiplication保证散列值对于单个字符串的任何置换都是不变的。散列值的唯一性由fundamental theorem of arithmetic(也称为唯一素因子分解定理)保证。
置换解
当字符串很小时,使用itertools.permutations()对目标字符串进行置换搜索是合理的(在an长度字符串上生成置换生成n阶乘候选者)。
好消息是,当n较小且单词数较大时,该方法运行非常快(因为集合隶属度测试为O(1)):
正如OP推测的那样,使用set.intersection()可以将纯python搜索循环加速到c-speed:
最佳解决方案
最佳解决方案取决于字符串的长度和单词的长度。计时将显示哪个最适合特定问题。
以下是使用两种不同字符串大小的不同方法的比较计时:
结果表明,对于小字符串,最快的方法是使用集合交集搜索目标字符串上的置换。
对于较大的字符串,最快的方法是传统的排序和比较解决方案。
希望你发现这个小小的算法研究和我一样有趣。外卖包括:
定时设置
FWIW,这是我用来运行比较计时的测试设置:
显然,您希望输出按字母顺序排序,所以应该这样做:
您只需使用
collections.Counter()
将words
与string
进行比较,而不必创建所有permutations
(这会随着字符串长度而爆炸):注意:
set
s是无序的,因此如果需要特定的顺序,可能需要对结果进行排序,例如return sorted(...)
相关问题 更多 >
编程相关推荐