首页 > 代码库 > Scramble String

Scramble String

2024-07-18 15:55:53   226人阅读

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.

思路：枚举所有的分割点。假设s1={ s11, s12 }，则可能的匹配方式为：s2={ scramble(s11), scramble(s12) }或者s2={ scramble(s12), scramble(s11) }。这样，记s2={s21,s22}，问题被分解为求解：isScramble(s11,s21) && isScramble(s12,s22) 和 isScramble(s11,s22) && isScramble(s12,s21)。显然，子问题的规模较原问题变小了。

        使用DP来求解该题，Q[step][i][j]记录以s1[i]起始长度为step+1的子串（即s1.substr(i,step+1)）和以s2[j]起始长度为step+1的子串（即s2.substr(j,step+1)）之间是否可转换。则，Q[step][i][j] = ( Q[k][i][j] && Q[step-k-1][i+k+1][j+k+1] ) || ( Q[k][i][j+step-k] && Q[step-k-1][i+k+1][j] )，其中，k=0, 1, ..., step-1，即依次取s1[i],s1[i+1],...,s1[step]作为子串s1.substr(i,step+1)的分割点。

 1 class Solution { 2 public: 3     bool isScramble( string s1, string s2 ) { 4         if( s1.length() != s2.length() ) { return false; } 5         int slen = s1.length(); 6         vector<vector<vector<bool>>> Q( slen ); 7         for( int step = 0; step < slen; ++step ) { 8             Q[step].resize( slen-step, vector<bool>( slen-step, false ) ); 9             vector<vector<bool>>& Qi = Q[step];10             if( step == 0 ) {11                 for( size_t i = 0; i != Qi.size(); ++i ) {12                     for( size_t j = 0; j != Qi[0].size(); ++j ) {13                         if( s1[i] == s2[j] ) { Qi[i][j] = true; }14                     }15                 }16             } else {17                 for( size_t i = 0; i != Qi.size(); ++i ) {18                     for( size_t j = 0; j != Qi[0].size(); ++j ) {19                         for( int k = 0; k < step; ++k )20                         {21                             if( ( Q[k][i][j] && Q[step-k-1][i+k+1][j+k+1] ) 22                             || ( Q[k][i][j+step-k] && Q[step-k-1][i+k+1][j] ) ) {23                                    Qi[i][j] = true;24                                    break;25                             }26                         }27                     }28                 }29             }30         }31         return Q.back()[0][0];32     }33 };

 


联系
我们