Problem 6
题目描述：
注意事项：
1.不能使用for while循环
2.达到limit时，必须立即返回，不能继续递归
代码：
1.我的代码，很繁琐
1 def shifty_shifts(start, goal, limit): 2 """A diff function for autocorrect that determines how many letters 3 in START need to be substituted to create GOAL, then adds the difference in 4 their lengths. 5 """ 6 # BEGIN PROBLEM 6 7 #base case should about limit ,the recursion should stop when reach limitation , 8 if limit<0: 9 return 1 10 #base case 11 len_sta = len(start) 12 len_goa = len(goal) 13 dif=abs(len_sta-len_goa) 14 15 if len_sta != len_goa: 16 limit-=dif 17 18 sum=dif 19 array_sta = list(start) 20 array_goa = list(goal) 21 if array_sta[0]!=array_goa[0]: 22 limit-=1 23 sum+=1 24 if len_goa==1 or len_sta==1: 25 return sum 26 min_len=min(len_sta,len_goa) 27 sum+=shifty_shifts(array_sta[1:min_len],array_goa[1:min_len],limit) 28 return sum
2.优秀的、优雅的代码
1 def shifty_shifts(start, goal, limit): 2 """A diff function for autocorrect that determines how many letters 3 in START need to be substituted to create GOAL, then adds the difference in 4 their lengths. 5 """ 6 # BEGIN PROBLEM 6 7 if len(start) == 0: 8 return len(goal) 9 if len(goal) == 0: 10 return len(start) 11 if start[0] != goal[0]: 12 if limit == 0: 13 return 1 14 return 1 + shifty_shifts(start[1:], goal[1:], limit - 1) 15 else: 16 return shifty_shifts(start[1:], goal[1:], limit)
Problem7
题目描述：
代码：
1 def meowstake_matches(start, goal, limit): 2 """A diff function that computes the edit distance from START to GOAL.""" 3 4 if limit < 0: 5 # BEGIN 6 "*** YOUR CODE HERE ***" 7 return 0 8 # END 9 10 elif len(start) == 0 or len(goal) == 0: 11 # BEGIN 12 "*** YOUR CODE HERE ***" 13 return len(start) + len(goal) 14 # END 15 elif start[0] == goal[0]: 16 return meowstake_matches(start[1:], goal[1:], limit) 17 else: 18 add_diff = meowstake_matches(start, goal[1:], limit - 1) 19 remove_diff = meowstake_matches(start[1:], goal, limit - 1) 20 substitute_diff = meowstake_matches(start[1:], goal[1:], limit - 1) 21 # BEGIN 22 "*** YOUR CODE HERE ***" 23 return 1 + min(min(add_diff, remove_diff), substitute_diff) 24 # END
反思：
1.题目已经给出明显的提示，并且自己也已经明显地感知到必须使用递归，但是并没有去按照自己总结的套路去做。所以以后一旦确定要用递归，那么就一定要按照套路去做。即先找好base case ，从最简单的案列开始，找出限定条件，再去想复杂的。
2.对事物的本质还是没有进行深刻的洞察。不能站在人的角度去思考，而是要站在机器的角度，计算机的角度。
譬如这一题，如果站在人的角度，肯定是一眼确定最大的相似位置，再来进行增删改。
但是站在机器的角度，这样子是无法进行的——不能找出最大的相似位置。
而题目已经给出提示，虽然仍然有所误导：提示是电脑只能一次处理一个，进行增删改，误导是直接到确定位置进行增删改。
而且最大的误导就是让人以为还要进行纠正，而不是简简单单的找出需要修改的次数。
3.最后return 中的1 是第一个字符位置的处理
对于每个字符，都需要进行至少一次操作才能匹配成功。因此，在进行插入、删除、替换操作之前，需要先将当前字符与目标字符串中对应位置的字符进行比较，以确定是否需要进行操作。
而对于起始字符串和目标字符串的第一个字符，它们之间的距离是由于它们不相同而产生的，因此需要进行一次操作才能匹配成功。因此，在进行插入、删除、替换操作之前，需要先将这两个字符进行比较，以确定是否需要进行操作。然后再将两个字符串都向后移动一位，继续进行递归调用，计算下一个字符的编辑距离。
因此，在计算编辑距离时，对于每个字符，都需要进行至少一次操作才能匹配成功，因此最小代价加上1就是当前字符的编辑距离。同时，在计算起始字符串和目标字符串的编辑距离时，也需要考虑它们的第一个字符是否匹配成功。
4.既然是要进行递归，那么肯定是首先处理一个，然后递归处理剩下的，那么问题就在于如何处理，处理谁。
如何处理，只有三种情况：增加，删除，替换。
增加，那么start第一个字符位置肯定相同了，原来的第一个字符位置移到二号位置，那么就比较二号位置呗。ok，goal [1:].
删除，那么start二号位置变为一号位置，goal还是没变，那么就继续比较一号位置呗。ok，start[1:]
替换，肯定二者一号位置都相同了，而且没有造成字符位置的变化，ok，那就同时比较后面的位置呗。start[1:] goal[1:]
但是注意每次只能处理一个，而且不知道谁才是最优的。那么都进行呗，最后取最优解，反正只是记录下处理次数。就像进行并行实验，只留下最好的，垃圾的都砍掉。
处理谁：
处理第一个元素，有两种情况：元素相同或者元素不同。
元素相同好解决，两个字符串都移位呗。元素不同，那么肯定会有一个change，这就是后面return 加一的由来。只是这个change是怎样的，就回到如何处理的问题了。