我的代码需要帮助。我需要将一个输入单词转换为另一个输入单词，一次更改一个字母。目前，我的程序执行此操作，但是效率很低，并且找不到最短的路径。任何帮助，将不胜感激。
import re
def same(item, target):
return len([c for (c, t) in zip(item, target) if c == t])
def build(pattern, words, seen, list):
return [word for word in words
if re.search(pattern, word) and word not in seen.keys() and
word not in list]
def find(word, words, seen, target, path):
list = []
for i in range(len(word)):
list += build(word[:i] + "." + word[i + 1:], words, seen, list)
if len(list) == 0:
return False
list = sorted([(same(w, target), w) for w in list])
for (match, item) in list:
if match >= len(target) - 1:
if match == len(target) - 1:
path.append(item)
return True
seen[item] = True
for (match, item) in list:
path.append(item)
if find(item, words, seen, target, path):
return True
path.pop()
fname = 'dictionary.txt'
file = open(fname)
lines = file.readlines()
while True:
start = input("Enter start word:")
words = []
for line in lines:
word = line.rstrip()
if len(word) == len(start):
words.append(word)
target = input("Enter target word:")
break
count = 0
path = [start]
seen = {start : True}
if find(start, words, seen, target, path):
path.append(target)
print(len(path) - 1, path)
else:
print("No path found")
编辑：以下是我通过尝试其他方法来解决此问题的另一次失败尝试。这次似乎无法正确循环。
def find(start, words, target): # find function. Word = start word, words =
start=list(start)
target=list(target)
print("Start word is ", start)
print("Target word is ", target)
letter = 0
while start != target:
if letter == len(target):
letter = 0
continue
elif start[letter] == target[letter]:
letter = letter + 1
continue
else:
testword = list(start)
testword[letter] = target[letter]
testword = ''.join(testword)
if testword in words:
start[letter] = target[letter]
letter = letter + 1
print(start)
continue
else:
letter = letter + 1
continue
letter = letter + 1
continue
fname = "dictionary.txt"
file = open(fname) # Open the dictionary
lines = file.readlines() # Read each line from the dictionary and store it in lines
while True: # Until ended
start = input("Enter start word:") # Take a word from the user
words = [] # Inititialise Array 'words'
for line in lines: # For each line in the dictionary
word = line.rstrip() #strip all white space and characters from the end of a string
if len(word) == len(start):
words.append(word)
if start not in words:
print("Your start word is not valid")
continue
target = input("Enter target word:")
if len(start) != len(target):
print("Please choose two words of equal length")
continue
if target not in words:
print("Your target word is not valid")
continue
break
编辑：这是代码的基本算法。 （两种变体都符合我的目的）。
-input start word
-input target word
- if len(start) = len(target)
continue
-check dictionary to see if target and start words are present
- find what letters are different from the start to target word
- change one different letter in the start word until start word
=target
word #after each letter change, output must be valid word in dictionary
The goal is to achieve this in the least amount of steps which is not achieved, the first section of code does this, I think but in a huge amount of steps I know could be far more efficient
最佳答案
这是不使用任何第三方模块的广度优先搜索。我不保证它会找到最短的解决方案，但它似乎可以工作。 ;）在找到解决方案时停止，但是由于集合的随机顺序，程序的每次运行都可能为给定的开始和目标对找到不同的解决方案。
import re
# The file containing the dictionary
fname = '/usr/share/dict/words'
start, target = 'hide', 'seek'
wlen = len(start)
wrange = range(wlen)
words = set()
with open(fname) as f:
for word in f:
w = word.rstrip()
# Grab words of the correct length that aren't proper nouns
# and that don't contain non-alpha chars like apostrophe or hyphen
if len(w) == wlen and w.islower() and w.isalpha():
words.add(w)
print('word set size:', len(words))
# Build a regex to find words that differ from `word` by one char
def make_pattern(word):
pat = '|'.join(['{}.{}'.format(word[:i], word[i+1:]) for i in wrange])
return re.compile(pat)
# Find words that extend each chain of words in `seq`
def find(seq):
result = []
seen = set()
for current in seq:
pat = make_pattern(current[-1])
matches = {w for w in words if pat.match(w)} - seen
if target in matches:
return current + (target,)
result.extend(current + (w,) for w in matches)
seen.update(matches)
words.difference_update(matches)
seq[:] = result
# Search for a solution
seq = [(start,)]
words.discard(start)
while True:
solution = find(seq)
if solution:
print(solution)
break
size = len(seq)
print(size)
if size == 0:
print('No solutions found')
break
典型输出
word set size: 2360
9
55
199
479
691
('hide', 'hire', 'here', 'herd', 'heed', 'seed', 'seek')
我应该提到的是，所有这些词链都占用了一些RAM，我将尝试考虑一种更紧凑的方法。但这在现代机器上应该不是真正的问题，除非您使用的是很大的单词。
关于python - 将源词转换成目标词，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45785582/