您的位置: 首页  >  IT文章  >  一路简单的题让你初步理解什么叫算法什么叫路径

一路简单的题让你初步理解什么叫算法什么叫路径

分类: IT文章 • 2022-07-27 16:44:14
一道简单的题让你初步理解什么叫算法什么叫路径

一道简单的题让你初步理解什么叫算法什么叫路径

书上看到的题目加上自己的理解，记录一下，题目本身不难理解，也比较初级，只是为了让大家对算法和路径的概念有个简单的认识
自己写的时候，开始思路完全不对，陷阱也挺多的，后来逐步理解了路径的含义

 

题目：

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-8
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'
'''已知一个字典、开始单词、结束单词，设计一个程序，要求每次只改变一个字母，改变后的单词必须存在于字典，最终变成结束单词'''

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 resultList

def 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 words


import time
time1 = time.time()  
result = transform(startWord, stopWord, dictory)
time2 = time.time()
print round(time2 - time1, 3)
print '->'.join(result)



 附上运行结果：

一路简单的题让你初步理解什么叫算法什么叫路径

相关推荐