一道简单的题让你初步理解什么叫算法什么叫路径
一道简单的题让你初步理解什么叫算法什么叫路径书上看到的题目加上自己的理解，记录一下，题目本身不难理解，也比较初级，只是为了让大家对算法和路径的概念有个简单的认识自己写的时候，开始思路完全不对，陷阱也挺多的，后来逐步理解了路径的含义
题目：
dictory = ['JKRE' ,'WESO' ,'LIVE' ,'VURR' ,'LAMP' ,'WEDO' ,
'JPRI' ,'LIME' ,'VESY' ,'JYRY' ,'TIPP' ,'LIPZ' ,
'WEIO' ,'WIPO' ,'FESA' ,'MIKE' ,'PURY' ,'LIPE' ,
'IESO' ,'PURE' ,'EURY' ,'VKES' ,'CATO' ,'JURY' ,
'TIPO' ,'LIMP' ,'FEAA' ,'PSVT' ,'SDOE' ,'WIIO' ,
'WEYS' ,'VEDO' ,'DAMP' ,'VURI' ,'EESY' ,'JPRE' ,
'PESO' ,'JKSE' ,'KURY' ,'ZESY' ,'OKDE' ,'ZESO' ,
'EURR' ,'LIPP' ,'EERY' ,'PSSO' ,'PESA' ,'VSSO' ,
'FKSE' ,'ZIKE' ,'SDKE' ,'VESO' ,'KDOE' ,'DESO' ,
'JDEO' ,'PIPE' ,'PLRE' ,'JYRI' ,'PIPO' ,'LIKE' ,
'NIKE' ,'TIPE' ,'AEIO' ,'HEOI' ,'OKEE' ,'AKES' ,
'JLRE']
startWord = 'DAMP'
stopWord = 'VURI'
'''已知一个字典、开始单词、结束单词，设计一个程序，要求每次只改变一个字母，改变后的单词必须存在于字典，最终变成结束单词'''
第一次把这道题给朋友看的时候，大家都不以为然，答案也是五花八门，有说用正则的，也有说匹配的
其实这道题是一道比较经典的涉及到算法的题目
里面有很多陷阱，最终的结果是DAMP->LAMP->LIMP->LIME->LIPE->TIPE->TIPO->......->VURI
下面说一下具体的思路：
1.传入单词，找到所有只改变一个字母的单词组合，比如'DAMP'，只改变一个字母的话，结果集有
['AAMP', 'BAMP', 'CAMP', 'EAMP', 'FAMP', 'GAMP', 'HAMP', 'IAMP', 'JAMP', 'KAMP', 'LAMP', 'MAMP', 'NAMP', 'OAMP', 'PAMP', 'QAMP', 'RAMP', 'SAMP', 'TAMP', 'UAMP', 'VAMP', 'WAMP', 'XAMP', 'YAMP', 'ZAMP', 'DBMP', 'DCMP', 'DDMP', 'DEMP', 'DFMP', 'DGMP', 'DHMP', 'DIMP', 'DJMP', 'DKMP', 'DLMP', 'DMMP', 'DNMP', 'DOMP', 'DPMP', 'DQMP', 'DRMP', 'DSMP', 'DTMP', 'DUMP', 'DVMP', 'DWMP', 'DXMP', 'DYMP', 'DZMP', 'DAAP', 'DABP', 'DACP', 'DADP', 'DAEP', 'DAFP', 'DAGP', 'DAHP', 'DAIP', 'DAJP', 'DAKP', 'DALP', 'DANP', 'DAOP', 'DAPP', 'DAQP', 'DARP', 'DASP', 'DATP', 'DAUP', 'DAVP', 'DAWP', 'DAXP', 'DAYP', 'DAZP', 'DAMA', 'DAMB', 'DAMC', 'DAMD', 'DAME', 'DAMF', 'DAMG', 'DAMH', 'DAMI', 'DAMJ', 'DAMK', 'DAML', 'DAMM', 'DAMN', 'DAMO', 'DAMQ', 'DAMR', 'DAMS', 'DAMT', 'DAMU', 'DAMV', 'DAMW', 'DAMX', 'DAMY', 'DAMZ']
2.在这个结果集中找到在字典中存在的，这里是第一个陷阱，因为我们很有可能找到不只一个单词在字典中，比如我们找到了DAMP和JAMP
其实这一步就相当于有两条路径，很有可能有一条路径最终不能到达最终的那个'VURI'单词
# 举个例子：
# 开始单词是LIKE，结束单词是GIVE，字典是[LIKE, ZIKE, LIVE, DIKE, DIVE, NIKE, GIVE]
#
# 第一次替换匹配
# LIKE ZIKE
# LIKE LIVE
# 第二次匹配替换
# ZIKE DIKE
# LIVE DIVE
# 第三次匹配替换
# DIKE NIKE
# DIVE GIVE
#
# 最后我想要的是GIVE
# 根据trackMap反向取路径GIVE->DIVE->LIVE->LIKE，搞定！
#看到了吧，这里相当于我们最开始从LIKE开始，匹配到ZIKE和LIVE，相当于我们有两条路径：
LIKE->ZIKE->DIKE->NIKE
LIKE->LIVE->DIVE->GIVE
这两条路径都满足每次只改变一个单词，但是只有第二条才能到达我们的最终目的地GIVE
3.所以我们要有一个MAP来保存所有可能的路径
4.下面就是把每次匹配的新词加入到路径里，当然也要判断是不是之前已经访问过，visitedList就是做这个判断用的，而actionList是用来保存需要去寻找路径的新单词
5.最后当我们终于匹配到结束单词'VURI'的时候，我们就开始反向来取trackMap里的路径，一步步倒着取路径经过的点，也就是每个单词，最后退出
这个例子很小，但是很经典，相信仔细看过这个例子，可以让你对最简单的算法和路径有个直观的印象
下面附上代码：
#coding:utf-8dictory = ['JKRE' ,'WESO' ,'LIVE' ,'VURR' ,'LAMP' ,'WEDO' ,'JPRI' ,'LIME' ,'VESY' ,'JYRY' ,'TIPP' ,'LIPZ' ,'WEIO' ,'WIPO' ,'FESA' ,'MIKE' ,'PURY' ,'LIPE' ,'IESO' ,'PURE' ,'EURY' ,'VKES' ,'CATO' ,'JURY' ,'TIPO' ,'LIMP' ,'FEAA' ,'PSVT' ,'SDOE' ,'WIIO' ,'WEYS' ,'VEDO' ,'DAMP' ,'VURI' ,'EESY' ,'JPRE' ,'PESO' ,'JKSE' ,'KURY' ,'ZESY' ,'OKDE' ,'ZESO' ,'EURR' ,'LIPP' ,'EERY' ,'PSSO' ,'PESA' ,'VSSO' ,'FKSE' ,'ZIKE' ,'SDKE' ,'VESO' ,'KDOE' ,'DESO' ,'JDEO' ,'PIPE' ,'PLRE' ,'JYRI' ,'PIPO' ,'LIKE' ,'NIKE' ,'TIPE' ,'AEIO' ,'HEOI' ,'OKEE' ,'AKES' ,'JLRE']startWord = 'DAMP'stopWord = 'VURI''''已知一个字典、开始单词、结束单词，设计一个程序，要求每次只改变一个字母，改变后的单词必须存在于字典，最终变成结束单词'''def transform(startWord, stopWord, dictionary): '''路径处理搜索''' actionList = [] visitedList = [] trackMap = {} startWord = startWord.upper() stopWord = stopWord.upper() actionList.append(startWord) visitedList.append(startWord) while len(actionList) > 0: w = actionList.pop() for v in getOneEditWords(w): if v in dictory: if v not in visitedList: actionList.append(v) visitedList.append(v) #这里可能一次查询到多个满足条件的路径，比如LIKE可能匹配出ZIKE,LIVE等 trackMap.setdefault(v, w) if v == stopWord: resultList = [] resultList.append(v)# 这里是代码的最后，也是核心，类似于路径，每次取出一次走过的路径，倒着来取，从最后的路径一直取到最开始的路径# 举个例子：# 开始单词是LIKE，结束单词是GIVE，字典是[LIKE, ZIKE, LIVE, DIKE, DIVE, NIKE, GIVE]## 第一次替换匹配# LIKE ZIKE# LIKE LIVE# 第二次匹配替换# ZIKE DIKE# LIVE DIVE# 第三次匹配替换# DIKE NIKE# DIVE GIVE# # 最后我想要的是GIVE# 根据trackMap反向取路径GIVE->DIVE->LIVE->LIKE，搞定！ key = v while True: if trackMap.has_key(key): key = trackMap.get(key) resultList.insert(0, key) else: break return resultListdef getOneEditWords(word): '''返回只改变一个字母的单词列表''' words = [] for index, value in enumerate(word): word_list = [w for w in word] c = ord('A') while c <= ord('Z'): if chr(c) != value: word_list[index] = chr(c) word_tmp = '' for t in word_list: word_tmp += t words.append(word_tmp) c+=1 return wordsimport timetime1 = time.time() result = transform(startWord, stopWord, dictory)time2 = time.time()print round(time2 - time1, 3)print '->'.join(result)附上运行结果：
