LeetCode日本語修行3日目- [87-Scramble String]


Scramble String

参考:https://leetcode.com/problems/scramble-string/

問題の内容

今日の問題、難しい...
一知半解の状態で、説明がつかない
解答は、他のコードを参考して書きました。
先にコードを記録きます...

class Solution {
     lateinit var solution: Array<Array<ByteArray>>
        fun isScramble(s1: String, s2: String): Boolean {
            var n = s1.length;
            var m = s2.length;
            if (n != m) {
                return false;
            }
            solution = Array(n, { Array(n, { ByteArray(n) } ) } )
            return myScramble(s1.toByteArray() ,0 ,n - 1 ,s2.toByteArray() ,0,n-1)
        }

       fun myScramble( s1:ByteArray , start1:Int , end1:Int , s2:ByteArray , start2:Int , end2:Int): Boolean {
            if(start1 == end1) return s1[start1] == s2[start2];
            if(solution[start1][start2][end1 - start1].toInt()!=0) return solution[start1][start2][end1 - start1] > 0;
            for (i in 0 until end1 - start1) {
                if( (myScramble(s1 ,start1 ,start1+ i ,s2 ,start2 ,start2 + i) &&
                            myScramble(s1 ,start1 + i + 1,end1 ,s2 ,start2+i+1,end2) ) // x + y
                    ||
                    (myScramble(s1 ,start1 ,start1 + i ,s2,end2 - i,end2) &&
                            myScramble(s1 ,start1 + i + 1,end1 ,s2 ,start2 ,end2 - i -1)) // y + x
                ) {
                    solution[start1][start2][end1 - start1] = 1;
                    return true;
                }
            }
            solution[start1][start2][end1 - start1] = -1;
            return false;
        }
}