We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
There was an error while loading. Please reload this page.
1 parent 2ea8ddf commit 927daadCopy full SHA for 927daad
DFS/332.Reconstruct-Itinerary/Readme.md
@@ -35,6 +35,6 @@ A -> B <-> F
35
36
那我们构造欧拉路径的思想是:B + path2 + path1,其中path1是从B点出发,选择任意支路并能够顺利走到终点的欧拉路径。path2是在path1走完之后,再从B点出发,最终走回B点的路径。注意,如果足够幸运,path1走遍了B后面的所有边,那么path2就不存在了。
37
38
-因为我们要最小化字典序,所以我们每次的分叉总会优先选择字典序较小的一支。如果这一支是类似上例中的"->D->E"这样直通到底的path1,那我们也无能为力,D注定是无法往前提的;否则的话我们就会先进入path2,从而更小化了整个欧拉路径的字典序。
+因为我们要最小化字典序,所以我们每次的分叉总会优先选择字典序较小的一支。有人会问,这样一定能得到欧拉路径吗?我们看上面的例子,在B点时,我们依据最小字典序会选择走D,即"->D->E",发现这是一条直通到底的path1;然后回溯到B点,此时再选择走F,得到“->F->B”,这其实是一个path2. 根据规则最终构建的路径是“B + path2 + path1”,可见依然保证是一条欧拉路径,
39
40
[Leetcode Link](https://leetcode.com/problems/reconstruct-itinerary)
0 commit comments