hiho一下第304周《合并子目录》题目分析

1
0

本题同 《统计子目录》 类似,都是trie的题目。

首先一样是将所有文件名都插入的trie中。

”合并子目录“这个要求,可以看作是要把trie中的某些节点的字符从'/'改为'-'。一个字符是'/'的节点需要改为'-',当且仅从它到它之后的下一个'/'之间每个节点都只有唯一的子节点。

于是我们可以DFS整个trie树,一旦遇到某个节点(不妨称之为V节点)字符是'/',就从这个字符开始,看看是不是只有唯一的子节点;如果是,那么再看看这个子节点是不是只有唯一的子节点……。 直到遇到分叉或者下一个'/'

如果先遇到分叉,意味着V不需要修改;如果先遇到下一个'/'说明V需要改成'-'

DSF完成之后,对于每一个终结点(文件名结尾),自底向上就可以得到合并之后的倒序文件名。

0 answer(s)

write answer 切换为英文 切换为中文


转发分享