search

apachecn / apachecn-algo-zh

ApacheCN 数据结构与算法译文集
https://algo.apachecn.org/
11k stars 2.19k forks source link

LC433 python wrong solution #224

Closed holyshipt closed 5 years ago

holyshipt commented 5 years ago

https://github.com/apachecn/awesome-algorithm/blob/master/docs/Leetcode_Solutions/Python/433._Minimum_Genetic_Mutation.md

DFS solution is wrong, run following test case: "AAC" "GCG" ["TAC","GAC","GAG","TAG", "TCG", "GCG"]

should be 3 not 5

0xkookoo commented 5 years ago

gene string should be a 8-character long string, so your test case is invalid.

holyshipt commented 5 years ago

There's nothing about length of label(node), you could expand the label with exact same suffix, iow: "AACAAAAA" "GCGAAAAA" ["TACAAAAA","GACAAAAA","GAGAAAAA","TAGAAAAA", "TCGAAAAA", "GCGAAAAA"]

I think dfs based solution is hard to be perfect for shortest path problem inside a multipath strong connected graph.

0xkookoo commented 5 years ago

I don't think your comment is right, but my code has some problem, I have fixed it, you can check the new code with your test case, then you will find out dfs works for this kind of questions. The only difference between dfs and bfs using for this question is that bfs has to record all of the states towards the final state but dfs only need to record the previous state. In other words, dfs will cost more time, because it has to try every possibilities; bfs can easily find the shortest way to the final destination but will cost more space.

holyshipt commented 5 years ago

Your dfs solution looks fine now, however it's worst complexity as you mentioned, hence bfs/dijkstra.

0xkookoo commented 5 years ago

Agreed.