你如何检查两个字符串在字符串中任何一点的顺序是否相同？

Question

["word", "ordw"] = True
["word", "odrw"] = False

如何使用切片得到这个结果？

Answer 1

简单的蛮力 O(n^2) 解决方案：

>>> def same_cyclic(w1, w2):
...     return any(w1 == w2[i:] + w2[:i] for i in range(len(w2)))
... 
>>> same_cyclic("word", "ordw")
True
>>> same_cyclic("word", "odrw")
False

优化它会是一个有趣的部分——如果单词中至少有一个独特的字母，你可以通过旋转使那个字母排成一行并进行一次比较来将它降低到 O(n) .

对于一般情况，我想我会使用 Counter 来找到最独特的字母，然后每次出现该字母时尝试一种排列，这应该说明这两个词可能排列的所有可能方式。那会有 O(m*n) 的时间复杂度，其中 m 是出现频率最低的字母的出现次数。

你如何检查两个字符串在字符串中任何一点的顺序是否相同？

How do you check if two strings are in the same order at any point in the string?

python

string

slice