주제 시리즈: Scramble String – 3D 동적 계획

제목:
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.
 
참조:
http://www.blogjava.net/sandy/archive/2013/05/22/399605.html문제풀이 부분을 인용하다
http://blog.csdn.net/fightforyourdream/article/details/17707187
"복잡한 문제에 대처하는 방법은 간단한 특례로 생각해서 규칙을 찾아내는 것이다. 간단한 상황을 먼저 살펴보자. 문자열의 길이는 1: 분명하다. 두 문자열은 완전히 같아야 한다. 문자열의 길이는 2: s1=ab로 하면 s2는'ab'또는'ba'만 가능하다. 임의의 길이의 문자열에 대해 우리는 문자열 s1을 a1, b1 두 부분으로 나눌 수 있다. s2는 a2, b2 두 부분으로 나누어 만족(a1~a2) & (b1~b2)) 또는 (a1~b2) & (a1~b2)"
 
"여기 3차원 그룹 boolean result [len] [len] [len]을 사용했습니다. 그 중에서 1차원은 하위 문자열의 길이이고 2차원은 s1의 시작 인덱스이며 3차원은 s2의 시작 인덱스입니다. result[k][i][j]는 s1[i...i+k]가 s2[j...j+k]로 바뀔 수 있는지 여부를 나타냅니다."

        if(s1==null || s2==null||s1.length()!=s2.length()) return false;

        int len = s1.length();

        boolean[][][] dp = new boolean[len][len][len];

        char[] c1 = s1.toCharArray();

        char[] c2 = s2.toCharArray();

        

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

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

                dp[0][i][j] = c1[i]==c2[j];

            }

        }

        for(int k=2;k<=len;k++){ 

            for(int i=len-k;i>=0;i--){ // the order is from the base, i.e. begin from the last position

                for(int j=len-k;j>=0;j--){

                    boolean r = false;  // test if cut anywhere within k length, the scramble exists

                    for(int cut=1;!r&&cut<k;cut++){ // !r&&        cut   

                        r = (dp[cut-1][i][j]&&dp[k-cut-1][i+cut][j+cut])||(dp[cut-1][i][j+k-cut]&&dp[k-cut-1][i+cut][j]); //   &&    ||    &&   

                    }

                    dp[k-1][i][j]=r; // can r go through all cuts within k?

                }

            }

        }

        return dp[len-1][0][0];

    }

비슷한 제목이 있을 거예요.
Interleaving String