真心求教一题，来自于地里面经OA

https://www.1point3acres.com/bbs/thread-810060-1-1.html

给你一列表的歌，返回最长的歌单，要求歌单第一首歌是input list的第一个,之后每一首歌的开头第一个单词，是前一首歌的最后一个单词。
如果两个歌单一样长，应当返回alphabetically smaller的歌‍‌‍‌‌‌‌‍‌‍‌‌‍‍‍‍‍‌‌‍单。

这题想了很久都不知道怎么解，希望各位帮帮忙，给个比较清楚的解。

如果A歌的最后一个单词和B歌的最后一个单词一样，那么就说明从A到B有一条有向边，最长的歌单就是整张图中最长的路径。也没啥太好的方法，就是DFS的过程中记录下目前最长的歌单最后返回一下。

lyyc 发表于 2022-2-26 22:18
如果A歌的最后一个单词和B歌的最后一个单词一样，那么就说明从A到B有一条有向边，最长的歌单就是整张图中最 ...

那得把所有的路径都存下来吧？放到一起，最后再排序？

SlayerEcho 发表于 2022-02-27 10:30:08
那得把所有的路径都存下来吧？放到一起，最后再排序？

不用呀，用一个全局变量记录最长的就好了

lyyc 发表于 2022-2-27 10:37
不用呀，用一个全局变量记录最长的就好了

那在相同长度下，怎么才能知道是不是alphabetically smaller呢？如果您有时间，可以写个code给我么？我想了好久了，都没想出来。

这题backtrack 把所有情况都尝试一遍就 每次有新的解的时候和当前解比较，如果比当前解法更优就存起来，否则扔掉