Python 動態規劃演算法,計算單詞距離
07-18
http://www.oschina.net/code/snippet_16840_16262010 1.[代碼][Python]代碼
| 123456789101112131415161718192021222324252627282930313233 | #!/usr/bin/env python#coding=utf-8def word_distance(m,n):"""compute the least steps number to convert m to n by insert , delete , replace .動態規劃演算法,計算單詞距離>>> print word_distance("abc","abec")1>>> print word_distance("ababec","abc")3"""len_1=lambda x:len(x)+1c=[[i] for i in range(0,len_1(m)) ]c[0]=[j for j in range(0,len_1(n))]for i in range(0,len(m)):# print i," ",for j in range(0,len(n)):c[i+1].append(min(c[i][j+1]+1,#插入n[j]c[i+1][j]+1,#刪除m[j]c[i][j] + (0 if m[i]==n[j] else 1 )#改))# print c[i+1][j+1],m[i],n[j]," ",# print ""return c[-1][-1]import doctestdoctest.testmod()raw_input("Success!") |
推薦閱讀：
※10分鐘搞懂遺傳演算法(含源碼)
※【目標追蹤】Learning Multi-Domain Convolutional Neural Networks for Visual Tracking閱讀筆記
※有關餘數的簡單方法，不知道是新發現還是已知？
※魔錶玩具及「The Clock」
※排序（一）