Open xiaoming-lu opened 3 years ago
我们是打算 sort 一下 然后按倒序排列 比如 bdca, bda, bca, ba, b, a
并且有一个poss 来纪录 每一种LENGTH 最初始的index, POSS[1] = 4 POSS[2] = 3 POSS[3] = 1 POSS[4] = 0
然后我们从后面Index 开始
dp := make([]int, len(words)) for i := len(words) - 1; i >= 0; i-- { dp[i] = 1 for j := poss[len(words[i])+1]; j < len(words) && len(words[j]) == len(words[i])+1; j++ { if isPredecessor(words[j], words[i]) { dp[i] = max(dp[i], 1+dp[j]) } } res = max(res, dp[i]) } return res
word[I] 是小的 找word[J](多出一个字母的) 来判断 I 是否是 J 的pre 我觉的 我们应该是要UPDATE dp[j] = max ( dp[i] + 1, dp[j]) 这样 我们可以不断地往前推。 而且最开始要加一个condition if(dp[i] == 0 ) dp[i] = 1; 防止之前找到过PRE的被重新重置到1.
我不清楚 是不是我没太了解你的思路 但感觉你这个代码应该过不了吧。
@xiaomingLu036 (非常抱歉,回复晚了,这 2 周一直在忙公司的项目)我的 DP 可以过呀,刚刚提交的通过记录,https://leetcode.com/submissions/detail/534451164/。dp 中记录的是能与下标值为 i 构成前后驱字符串的个数。你如果是从 j 开始更新 dp 也可以实现。
我们是打算 sort 一下 然后按倒序排列 比如 bdca, bda, bca, ba, b, a
并且有一个poss 来纪录 每一种LENGTH 最初始的index, POSS[1] = 4 POSS[2] = 3 POSS[3] = 1 POSS[4] = 0
然后我们从后面Index 开始
word[I] 是小的 找word[J](多出一个字母的) 来判断 I 是否是 J 的pre 我觉的 我们应该是要UPDATE dp[j] = max ( dp[i] + 1, dp[j]) 这样 我们可以不断地往前推。 而且最开始要加一个condition if(dp[i] == 0 ) dp[i] = 1; 防止之前找到过PRE的被重新重置到1.
我不清楚 是不是我没太了解你的思路 但感觉你这个代码应该过不了吧。