[leetcode] 87. Scramble String

[leetcode] 87. Scramble String

Description

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = “great”:

great / \ gr eat / \ / \g r e at / \ a t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node “gr” and swap its two children, it produces a scrambled string “rgeat”.

rgeat / \ rg eat / \ / \r g e at / \ a t

We say that “rgeat” is a scrambled string of “great”.

Similarly, if we continue to swap the children of nodes “eat” and “at”, it produces a scrambled string “rgtae”.

rgtae / \ rg tae / \ / \r g ta e / \ t a

We say that “rgtae” is a scrambled string of “great”.

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Example 1:

Input:

s1 = "great", s2 = "rgeat"

Output:

true

Example 2:

Input:

s1 = "abcde", s2 = "caebd"

Output:

false

分析

题目的意思是：判断字符串s1和s2是不是scramble的。

递归版

s1和s2是 scramble 的话，那么必然存在一个在 s1 上的长度 l1，将 s1 分成 s11 和 s12 两段，同样有 s21 和 s22，那么要么 s11 和 s21 是 scramble 的并且 s12 和 s22 是 scramble 的；要么 s11 和 s22 是 scramble 的并且 s12 和 s21 是 scramble 的。例如：rgeat 和 great，rgeat 可分成 rg 和 eat 两段， great 可分成 gr 和 eat 两段，rg 和 gr 是scrambled的， eat 和 eat 当然是scrambled。

动态规划版

这其实是一道三维动态规划的题目，维护量 dp[i][j][n]，其中i是 s1 的起始字符，j是 s2 的起始字符，而n是当前的字符串长度，dp[i][j][len] 表示的是以i和j分别为 s1 和 s2 起点的长度为 len 的字符串是不是互为 scramble。首先是把当前 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 的。总结起来递推式是 dp[i][j][len] = || (dp[i][j][k] && dp[i+k][j+k][len-k] || dp[i][j+len-k][k]&&dp[i+k][j][len-k]) 对于所有 1<=k

代码一 递归版

class Solution {public: bool isScramble(string s1, string s2) { if(s1.length()!=s2.length()){ return false; } if(s1==s2){ return true; } string str1=s1; string str2=s2; sort(str1.begin(),str1.end()); sort(str2.begin(),str2.end()); if(str1!=str2){ return false; } for(int i=1;i

代码二 动态规划版

class Solution {public: bool isScramble(string s1, string s2) { if(s1.size()!=s2.size()){ return false; } int len=s1.length(); //dp[k][i][j] 表示s2的从j开始长度为k的子串是否为s1的从i开始长度为k的子串的scramble string bool dp[len+1][len][len]; memset(dp,0,sizeof(dp)); //初始化dp[1][i][j],长度为1的子串，只要相等就是scramble string for(int i=0;i

参考文献

​​[编程题]scramble-string​​​​[LeetCode] Scramble String 爬行字符串​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。