Scramble String -- LeetCode

时间:2021-09-19 18:00:00

原题链接: http://oj.leetcode.com/problems/scramble-string/ 

这道题看起来是比較复杂的,假设用brute force,每次做分割,然后递归求解,是一个非多项式的复杂度,一般来说这不是面试官想要的答案。

这事实上是一道三维动态规划的题目,我们提出维护量res[i][j][n],当中i是s1的起始字符,j是s2的起始字符,而n是当前的字符串长度,res[i][j][len]表示的是以i和j分别为s1和s2起点的长度为len的字符串是不是互为scramble。

有了维护量我们接下来看看递推式,也就是怎么依据历史信息来得到res[i][j][len]。推断这个是不是满足,事实上我们首先是把当前s1[i...i+len-1]字符串劈一刀分成两部分,然后分两种情况:第一种是左边和s2[j...j+len-1]左边部分是不是scramble,以及右边和s2[j...j+len-1]右边部分是不是scramble;另外一种情况是左边和s2[j...j+len-1]右边部分是不是scramble,以及右边和s2[j...j+len-1]左边部分是不是scramble。假设以上两种情况有一种成立,说明s1[i...i+len-1]和s2[j...j+len-1]是scramble的。而对于推断这些左右部分是不是scramble我们是有历史信息的,由于长度小于n的全部情况我们都在前面求解过了(也就是长度是最外层循环)。

上面说的是劈一刀的情况,对于s1[i...i+len-1]我们有len-1种劈法,在这些劈法中仅仅要有一种成立,那么两个串就是scramble的。

总结起来递推式是res[i][j][len] = || (res[i][j][k]&&res[i+k][j+k][len-k] || res[i][j+len-k][k]&&res[i+k][j][len-k]) 对于全部1<=k<len,也就是对于全部len-1种劈法的结果求或运算。由于信息都是计算过的,对于每种劈法仅仅须要常量操作就可以完毕,因此求解递推式是须要O(len)(由于len-1种劈法)。

如此总时间复杂度由于是三维动态规划,须要三层循环,加上每一步须要线行时间求解递推式,所以是O(n^4)。尽管已经比較高了,可是至少不是指数量级的,动态规划还是有非常大有事的,空间复杂度是O(n^3)。代码例如以下:

public boolean isScramble(String s1, String s2) {
if(s1==null || s2==null || s1.length()!=s2.length())
return false;
if(s1.length()==0)
return true;
boolean[][][] res = new boolean[s1.length()][s2.length()][s1.length()+1];
for(int i=0;i<s1.length();i++)
{
for(int j=0;j<s2.length();j++)
{
res[i][j][1] = s1.charAt(i)==s2.charAt(j);
}
}
for(int len=2;len<=s1.length();len++)
{
for(int i=0;i<s1.length()-len+1;i++)
{
for(int j=0;j<s2.length()-len+1;j++)
{
for(int k=1;k<len;k++)
{
res[i][j][len] |= res[i][j][k]&&res[i+k][j+k][len-k] || res[i][j+len-k][k]&&res[i+k][j][len-k];
}
}
}
}
return res[0][0][s1.length()];
}

个人认为这是LeetCode中最难的动态规划的题目了,要进行一次三维动态规划,对于维护量的含义也比較讲究。有朋友会讨论这个维护量是怎么提出来的,我自己也没什么绝对的方法,还是熟能生巧,靠“感觉”,做的题目多了就自然来了,这个做高中数学题有点类似哈,辅助线是靠“灵感”的哈。面试中假设遇到就是top难度的了,只是即使如此,仅仅要思路清晰,还是能够记住的。假设没做过,个人认为比較难当场想出来,只是算法大牛就另说了,这样的题非常常常出如今编程比赛中,ACM高手还是不在话下的哈。