擅长:python、mysql、java
<p>反复调用replace意味着每次替换都必须遍历整个字符串,即O(m*n)。取而代之的是:</p>
<pre><code>rep = dict(zip(arr1, arr2)) # make mapping, O(m)
result = ''.join(rep.get(ch, ch) for ch in st)
</code></pre>
<p>第一行是O(m),其中m是arr1和arr2的长度。你知道吗</p>
<p>第二行是O(n),其中n是st的长度</p>
<p>总的来说,这是O(m+n)而不是O(m*n),如果m或n很大,这是一个重大的胜利。你知道吗</p>