LeetCode 87. 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 / \ 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 / \ rg eat / \ / \ r g e at / \ a t
We say that
"rgeat"is a scrambled string of
Similarly, if we continue to swap the children of nodes
"at", it produces a scrambled string
rgtae / \ rg tae / \ / \ r g ta e / \ t a
We say that
"rgtae"is a scrambled string of
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
Input: s1 = "great", s2 = "rgeat" Output: true
Input: s1 = "abcde", s2 = "caebd" Output: false
You may considering the string is not always split at the middle.
The tree could be like this:
great / \ g reat / \ r eat ...
Divide And Conquer (Top to Down)
Dynamic Programming (Bottom to Up)
'l'is the length of substring, the
lengthin recursive solution.
dp[i][j] = (s1[i] == s2[j] ? true : false).
dp[l][i][j] = // isScramble(s1[k:], s2[k:]) && isScramble(s1[:k], s2[:k]) (dp[k][i][j] && dp[l-k][i+k][j+k]) || // isScramble(s1[k:], s2[:length-k]) && isScramble(s1[:k], s2[length-k:]) (dp[k][i][j+l-k] && dp[l-k][i+k][j])
k means split the
l to two parts, so
0 <= k <= l;