回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>给定一个输入字符串,我想找到<a href="https://en.wikipedia.org/wiki/Levenshtein_distance" rel="noreferrer">Levenshtein distance</a>2内所有其他字符串的集合。例如,如果输入字符串为“aaa”,字母表为['a','b'],则我们有:</p>
<blockquote>
<p>{'baaa', 'aab', 'a', 'aaaaa', 'baab', 'abbaa', 'abaa', 'aaabb', 'abb',
'aaab', 'ababa', 'aa', 'aabb', 'baba', 'baaab', 'aabab', 'aaaab',
'abaaa', 'aabaa', 'bbaaa', 'abaab', 'aaaa', 'baaaa', 'bab', 'bba',
'aba', 'aaaba', 'ba', 'aabba', 'abab', 'baa', 'aaa', 'bbaa', 'baaba',
'aaba', 'abba', 'ab', 'babaa'}</p>
</blockquote>
<p>我有代码来做这件事,但它是低效的。在这里,它使用所有可打印的ascii字符作为字母表和输入字符串<code>aaaaaaaaaa</code></p>
<pre><code>import string
input_string = "a" * 10
f = (
lambda input_string, dist=2, i=0: dist * input_string[i - 1 :]
and {
k[:i] + char + k[i + w:]
for k in f(input_string, dist - 1)
for char in [""] + list(string.printable)
for w in (0, 1)
}
| f(input_string, dist, i + 1)
or {input_string}
)
f(input_string)
</code></pre>
<p>我需要用不同的输入字符串运行多次。这段代码需要我桌面上当前的2.9秒来生成1631129个不同的字符串。有人知道如何使它更快吗</p>
<hr/>
<p>到目前为止的排名表(使用可打印字母表):</p>
<p>我的代码:2.98秒±146毫秒</p>
<p>阿兰T.的代码:1.58秒±60.7毫秒。目前的获胜者</p>
<p>ddg代码:1.85秒±28.4毫秒</p>