[Leetcode] scramble string 乱串

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.

题意：判断s2是否是s1的爬行字符串。

思路：如果s1和s2是scramble，那么必然存在一个在s1上的长度len1,将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。参考了Grandyang和Eason Liu的博客。

代码如下：

 class Solution {

 public:

     bool isScramble(string s1, string s2)

     {

         if(s1.size() !=s2.size())   return false;

         if(s1==s2)  return true;

         string str1=s1,str2=s2;

         sort(str1.begin(),str1.end());

         sort(str2.begin(),str2.end());

         if(str1 !=str2) return false;

         for(int i=;i<s1.size();++i)

         {

             string s11=s1.substr(,i);

             string s12=s1.substr(i);

             string s21=s2.substr(,i);

             string s22=s2.substr(i);

             if(isScramble(s11,s21)&&isScramble(s12,s22))

                 return true;

             else

             {

                 s21=s2.substr(s1.size()-i);

                 s22=s2.substr(,s1.size()-i);

                 if(isScramble(s11,s21)&&isScramble(s12,s22))

                     return true;

             }

         }

         return false;

     }

 };

注：substr()函数的用法：str.substr(start,Length)从某一位置start开始，指定长度为length的子字符串，若，length为0或者为负数返回空串；若，没有指定该参数，则，从指定位置开始直到字符串的最后。

方法二：动态规划，参见Grandyang的博客，维护量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的.

代码如下：

 class Solution {

 public:

     bool isScramble(string s1, string s2)

     {

         if(s1.size() !=s2.size())   return false;

         if(s1==s2)  return true;

         int len=s1.size();

         vector<vector<vector<bool>>> dp(len,

                     vector<vector<bool>>(len,vector<bool>(len+,false)));

         for(int i=;i<len;++i)

         {

             for(int j=;j<len;++j)

             {

                 dp[i][j][]=(s1[i]==s2[j]);

             }

         }

         for(int n=;n<=len;++n)

         {

             for(int i=;i<=len-n;++i)

             {

                 for(int j=;j<=len-n;++j)

                 {

                     for(int k=;k<n;++k)

                     {

                         if((dp[i][j][k]&&dp[i+k][j+k][n-k])||

                         (dp[i+k][j][n-k]&&dp[i][j+n-k][k]))

                         {

                             dp[i][j][n]=true;

                         }

                     }

                 }

             }

         }

         return dp[][][len];

     }

 };

巴特西

[Leetcode] scramble string 乱串

最新文章

热门文章