嗯嗯,这题啊,正解应该是trie树。
不过如果你够大佬,比如xzy,就可以用dfs轻松5msA掉。
而本蒟蒻的trie树不仅代码量>大佬xzy,而且还用了44ms。
真是失败。
好吧,思路是建立一棵trie树,然后对于字符串中的每一个字符,如果其前一个字符是某个单词的结尾,就深入这个trie树,并标记找到的所有单词结尾。注意最后一个字符也要特判。
代码: