杭电ACM 1503最短公共超串问题
字符串拼接的最短路径怎么走？杭电 ACM 1503 这个题目还蛮有意思的，拿来练练手刚刚好。主要场景是：给你两种水果的名字，比如apple和peach，你要拼出一个最短的新名字，要求这两个原词都得是它的子串。
嗯，听起来像是字符串匹配对吧？其实核心就是个最短公共超串的问题。做法也挺经典：动态规划。不过别被这三个字吓到，逻辑其实不难。你用两个二维数组，一个记录组合长度，一个记录怎么拼的，回溯一遍就能拿到结果。
比如输入apple和peach，你能拼出appleach，又短又不漏字符。代码实现主要是比对字符，看能不能接上，不能的话就另起一段拼接，类似字符串版的路径合并。
写这个的好处？嗯，一是练习 DP 的思路，二是对字符串能力有，尤其是你做前端或后端文本时，这种逻辑随处可见。反正逻辑清晰，练起来也不痛苦。
如果你想多看看其他的字符串技巧，比如逆置、正则或者FastStrings，下面这些资源也挺不错：
如果你刚好在刷题，或者项目里遇到类似字符串拼接的需求，这道题值得一看。
文件大小：5.27KB
评论区