{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"code","source":"str1 = 'abcdef'\nstr2 = 'azced'","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":" Levenshtein Distance : Minimum number of edits (insertion, deletion, or replacement) to tranform str1 to str2.","metadata":{}},{"cell_type":"markdown","source":"Watch the following video for the explanation.","metadata":{}},{"cell_type":"markdown","source":"https://youtu.be/We3YDTzNXEk","metadata":{}},{"cell_type":"code","source":"arr = [[None for _ in range(len(str1)+1)] for _ in range(len(str2)+1)]","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"for i in range(len(str2)+1):\n    arr[i][0] = i\n\nfor j in range(1, len(str1)+1):\n    arr[0][j] = j\n    arr[1][j] = j-1","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"arr","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"for i in range(2, len(str2)+1):\n    for j in range(1, len(str1)+1):\n\n        if str1[j-1] == str2[i-1]:\n            arr[i][j] = arr[i-1][j-1]\n\n        else:\n            arr[i][j] = min(arr[i-1][j], arr[i-1][j-1], arr[i][j-1]) + 1","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"arr","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"levenshtein_dist = arr[-1][-1]","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"levenshtein_dist","metadata":{"trusted":true},"execution_count":null,"outputs":[]}]}