擅长:python、mysql、java
<p>设给定的汉明距离为<em>D</em>,设<em>w</em>为“word”子串。从<em>w</em>,您可以通过深度限制<a href="https://en.wikipedia.org/wiki/Depth-first_search" rel="nofollow">depth-first search</a>生成距离≤<em>D</em>的所有单词:</p>
<pre><code>def dfs(w, D):
seen = set([w]) # keep track of what we already generated
stack = [(w, 0)]
while stack:
x, d = stack.pop()
yield x
if d == D:
continue
# generate all mutations at Hamming distance 1
for i in xrange(len(x)):
for c in set("ACGT") - set(x[i])
y = x[:i] + c + x[i+1:]
if y not in seen:
seen.add(y)
stack.append((y, d + 1))
</code></pre>
<p>(这绝不会很快,但可能会给人以启发。)</p>