买它Phone

求米看面筋…


2月10日裁员当天的面试……心情复杂，不过面试官似乎没受什么影响。三哥，短暂介绍后就迅速进入题目


第一题是给一个string类似

1. s = "catanddog"

复制代码

和一个list of str作为dictionary,

1. d = ["cat", "and", "dog"]

复制代码

，问

1. s

复制代码

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

第一题应该是依散酒的变形，因为面试的时候其实还要求如果能被拆分，要输出拆分后的结果，所以在DP和backtracking之间选了backtracking，但现在想想DP也行

要求输出拆分后的结果就是药似灵

匿名用户 发表于 2025-2-15 10:42
那时间复杂度的话应该很高吧，len(s) * n^(m)?
n - the number of words in wordDict
m - len(s)/avear ...

我觉得这样应该是对的！我当时在指数上一直绕不清楚，总以为是n^n，但又感觉过于离谱了，你这个m我觉得挺合理的。另外小小修改的话——如果只需要返回任意一个valid的结果的话，那时间复杂度应该可以不用乘那个len(s)

这样盘下来感觉还是DP性能好得多，不知道为啥他刚开始总不让我用……

匿名用户 发表于 2025-2-15 17:51
我觉得这样应该是对的！我当时在指数上一直绕不清楚，总以为是n^n，但又感觉过于离谱了，你这个m我觉得挺 ...

噢，所以最后就只返回一个valid path, e.g. ["leet","code"]?
我以为是把所有valid的结果返回e.g. [["leet","code"], ["lee","t","code"]]？

依散酒？

匿名用户 发表于 2025-2-15 07:39
依散酒？

感谢！应该是这个的变形，我在原帖子删更新一下~

backtracking 复杂度比较大哦，请问楼主过了吗？

buaawj 发表于 2025-2-15 09:45
backtracking 复杂度比较大哦，请问楼主过了吗？

过了……是挺晕的，其实一上来就提出用DP，结果面试官总不让用，说sure dp can work, is there a more straightforward way之类的，绕来绕去就有点晕，用了backtracking之后复杂度就没那么直观了。但不知道为啥最后飘过了，可能是也算满足了他的要求吧

要输出path的话你用上memoization了吗？感觉memory会挂掉？

匿名用户 发表于 2025-2-15 10:04
要输出path的话你用上memoization了吗？感觉memory会挂掉？

用了backtracking空间复杂度会好点，可以只维护一个list，下一步搜索的时候append，失败了退回来再pop。DP的话要设计得巧妙一点才不至于一直重复存目前list的copy

（现在想法一大堆，面试时候脑子全是浆糊…）

匿名用户 发表于 2025-2-15 13:08
用了backtracking空间复杂度会好点，可以只维护一个list，下一步搜索的时候append，失败了退回来再pop。D ...

那时间复杂度的话应该很高吧，len(s) * n^(m)?
n - the number of words in wordDict
m - len(s)/avearge word length in wordDict? dfs的深度
len(s) - 最后copy path进结果

空间复杂度是n^(m)？