擅长:python、mysql、java
<p>您可以使用<code>min</code>而不是排序:</p>
<pre><code>def normalized2(s):
return min(( s[i:] + s[:i] for i in range(len(s)) ))
</code></pre>
<p>但它仍然需要复制字符串<code>len(s)</code>次。更快的方法是过滤最小字符的起始索引,直到只得到一个。有效搜索最小循环:</p>
^{pr2}$
<p>对于长字符串,这要快得多:</p>
<pre><code>In [143]: loop = [ random.choice("abcd") for i in range(100) ]
In [144]: timeit normalized(loop)
1000 loops, best of 3: 237 µs per loop
In [145]: timeit normalized2(loop)
10000 loops, best of 3: 91.3 µs per loop
In [146]: timeit normalized3(loop)
100000 loops, best of 3: 16.9 µs per loop
</code></pre>
<p>但如果我们有很多重复的话,这种方法是不够的:</p>
<pre><code>In [147]: loop = "abcd" * 25
In [148]: timeit normalized(loop)
1000 loops, best of 3: 245 µs per loop
In [149]: timeit normalized2(loop)
100000 loops, best of 3: 18.8 µs per loop
In [150]: timeit normalized3(loop)
1000 loops, best of 3: 612 µs per loop
</code></pre>
<p>我们也可以向前扫描字符串,但我怀疑它是否会更快,没有一些花哨的算法。在</p>