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.
Example 1:
Input: s1 = "great", s2 = "rgeat" Output: true
Example 2:
Input: s1 = "abcde", s2 = "caebd" Output: false
Solution: Recursion
isScramble(s1, s2)
if s1 == s2: return true
if sorted(s1) != sroted(s2): return false
We try all possible partitions:
- s1[0:l] v.s s2[0:l] && s1[l:] vs s2[l:]
- s1[0:l] vs s2[L-l:l] && s1[l:] vs s2[0:L-l]
Time complexity: O(n^5)
Space complexity: O(n^4)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public: bool isScramble(string_view s1, string_view s2) { const int l = s1.length(); if (s1 == s2) return true; if (freq(s1) != freq(s2)) return false; for (int i = 1; i < l; ++i) if (isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i)) || isScramble(s1.substr(0, i), s2.substr(l - i, i)) && isScramble(s1.substr(i), s2.substr(0, l - i))) return true; return false; } private: vector<int> freq(string_view s) { vector<int> f(26); for (char c : s) ++f[c - 'a']; return f; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
# Author: Huahua class Solution: @lru_cache(maxsize=None) # optional def isScramble(self, s1: str, s2: str) -> bool: if s1 == s2: return True # important, TLE if commneted out if Counter(s1) != Counter(s2): return False L = len(s1) for l in range(1, L): if self.isScramble(s1[0:l], s2[0:l]) and self.isScramble(s1[l:], s2[l:]): return True if self.isScramble(s1[0:l], s2[L-l:]) and self.isScramble(s1[l:], s2[0:L-l]): return True return False |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment