朋友问我的，我想的是 用backtracking find all valid path，然后每个path 都会record the edit distance
最后挑出最少的
但是这 其中 要考虑 path 中的city 是否 valid， 然后path 是不是 考虑的也很多。。
因为用最少的 又想或许可以 dynamic programming
没有具体实施起来
所以在这问一下大家的想法，谢谢！！！
题是
输入是个map，含有city name，和这个cit相通的其他city
[
[AAA: [BBB, CCC, DDD]],
[BBB : [CCC, PPP]],
[PPP: [AAA]]
]
形成的graph是
PPP——AAA ——DDD
/
BBB —— CCC
输入还有个path，就是设定好的路线，但可能会有拼写失误 比如
-
example 1:
BAB -> AAA -> DDD 这条是没法跑的，但把BAB改成BBB就可以了，cost是1 -
example 2:
PPP -> BBB -> CCC 这条也没法跑，得再加个AAA，cost是3 -
example 3:
EEE -> AAA -> PPP map里没有出现EEE，但把EEE改成BBB或者DDD都可以，cost是3 -
example 4:
B -> A ->PAP， 把B变成BBB，A变成AAA，PAP改成PPP，cost是6
输出是求把这条路径变成能走路径的最小cost