LC433 python wrong solution

[holyshipt]

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]

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

[holyshipt]

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]

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]

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

[0xkookoo]

Agreed.