leetcode 87. Scramble String这道有动态规划的解法吗

Question

我是使用递归并且没加记忆化搜索解决这道问题的，但是实在想不到这道题的递推公式，请问波波老师又更好的方法解决这道题吗？

Answer 1

liuyubobobo 2018-04-24 04:08:43

简单看了一下，这个问题的测试数据不是特别好。用递归加剪枝反而时间最快。应该是测试数据太弱。Leetcode上题号比较靠前的问题普遍测试数据比较弱，可能因为偏面试，主要还是验证程序的正确性，题号靠后的问题越来越偏竞赛，虽然难度达不到，但是从题目表述，到测试用例的数量和对性能的要求，越来越高：）

Anyway，如果你实现了递归解法，递归函数主要应该是用于判断是s1和s2是否是scramble string，那么对于同样的s1和s2，可以引入记忆化搜索。虽然使用这种方式，貌似重叠子问题不会太多。我的实现（都是C++实现）：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0087-Scramble-String/cpp-0087/main2.cpp

可以将问题降到多项式级别的想法是，设计状态memo[len][i][j]，表示s1从i开始，长度为len的字符串，即s1[i, ...i + len -1] 与s2从j开始，长度为len的字符串，即s2[j,...j + len -1]，这两个长度均为len的字符串，是否为scramble string。状态转移的方式和递归表达的状态转移其实是一样的逻辑，只不过换了这样的状态表达。这样一来，最多只有O(n^3)个状态，在状态转移时，要加入一层循环，时间复杂度为O(n^4)的。对于这个思考的记忆化搜索，我的实现：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0087-Scramble-String/cpp-0087/main3.cpp

有了上面的状态，就可以自底向上的使用动态规划实现了。长度为1开始是最基本的情况，只要s1[i] == s2[j]，则memo[1][i][j]为true。在这个基础上，从长度为2开始，逐渐增加到长度为s1.length，对于每一个长度k，遍历s1和s2的所有起始索引i和j，根据更短的长度的结果，得到当前长度下的memo[k][i][j]的结果。最终问题的答案为memo[s1.size()][0][0]。我的实现：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0087-Scramble-String/cpp-0087/main4.cpp

这个状态的定义方式和状态转移的方式，如果第一次接触这样的问题，确实很难想出来。再多练习一些动态规划的题目，会发现这个状态的定义方式，还是很自然的：）

P.S. 我看到你问了一些Leetcode上Hard难度的题目。我不确定你在为什么做准备。Leetcode上大多数Hard级别的题目，在实际面试中，尤其是国内，即使是大厂，都近乎不会被考到。所以如果是面试准备的话，建议还是要巩固基础，切忌走偏。当然如果你是在准备竞赛的话，没毛病：）

加油！

• 提问者 站在巨人的肩膀上丶 #1

  非常感谢！

• 提问者 站在巨人的肩膀上丶 #2

  我感觉思考这种难题对我的思维水平提高有帮助，并且现在也不是很急着准备面试的东西，所以就会花些时间去思考一些较难的题目，谢谢波波老师的建议~