|
I did the recursive solution to edit distance first, but chickened out when I saw how slow it was for inputs above len(10). I tried using a cache to speed things up, and I saw in the answer video that he mentions that caching can help. I must have done something wrong, because I put some print statements in my code to see when the cache was being used, and it never was getting used. For some reason I can't find my recursive/cache solution (must have trashed it). I was hoping someone who used recursion AND caching in an effective manner would post their code here. I want to see where I went wrong. I'll copy my straight recursive function below. There's a middle part that truncates the strings in all the places where they match, but I suspect this doesn't speed things up, as the real cost is all the recursive calls themselves, not what they are doing: def edit_distance(s,t): |
|
This is the one I posted: http://www.udacity-forums.com/cs101/questions/61679/a-cached-version-of-peters-72-starred-solution |
|
This is Basically, you just provide cache for your function (as a global var or input parameter) and 1) check whether string pair is cached before doing more expensive computation and 2) if it isn't cached yet, add pair to cache before returning the answer. I'd suggest to put cache check before or after the 's==t' base case (I'm still not certain whether it's useful to cache identical strings). |
