Nav: << previous: 86.分隔链表 | next: 88.合并两个有序数组 >>
Description
tab: English
<p>We can scramble a string s to get a string t using the following algorithm:</p>
<ol>
<li>If the length of the string is 1, stop.</li>
<li>If the length of the string is > 1, do the following:
<ul>
<li>Split the string into two non-empty substrings at a random index, i.e., if the string is <code>s</code>, divide it to <code>x</code> and <code>y</code> where <code>s = x + y</code>.</li>
<li><strong>Randomly</strong> decide to swap the two substrings or to keep them in the same order. i.e., after this step, <code>s</code> may become <code>s = x + y</code> or <code>s = y + x</code>.</li>
<li>Apply step 1 recursively on each of the two substrings <code>x</code> and <code>y</code>.</li>
</ul>
</li>
</ol>
<p>Given two strings <code>s1</code> and <code>s2</code> of <strong>the same length</strong>, return <code>true</code> if <code>s2</code> is a scrambled string of <code>s1</code>, otherwise, return <code>false</code>.</p>
<p> </p>
<p><strong class="example">Example 1:</strong></p>
<pre>
<strong>Input:</strong> s1 = "great", s2 = "rgeat"
<strong>Output:</strong> true
<strong>Explanation:</strong> One possible scenario applied on s1 is:
"great" --> "gr/eat" // divide at random index.
"gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
"gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them.
"g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
"r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
"r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is "rgeat" which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.
</pre>
<p><strong class="example">Example 2:</strong></p>
<pre>
<strong>Input:</strong> s1 = "abcde", s2 = "caebd"
<strong>Output:</strong> false
</pre>
<p><strong class="example">Example 3:</strong></p>
<pre>
<strong>Input:</strong> s1 = "a", s2 = "a"
<strong>Output:</strong> true
</pre>
<p> </p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>s1.length == s2.length</code></li>
<li><code>1 <= s1.length <= 30</code></li>
<li><code>s1</code> and <code>s2</code> consist of lowercase English letters.</li>
</ul>
---
[submissions](https://leetcode.com/problems/scramble-string/submissions/) | [solutions](https://leetcode.com/problems/scramble-string/solutions/)
tab: 中文
使用下面描述的算法可以扰乱字符串 <code>s</code> 得到字符串 <code>t</code> ：
<ol>
<li>如果字符串的长度为 1 ，算法停止</li>
<li>如果字符串的长度 > 1 ，执行下述步骤：
<ul>
<li>在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 <code>s</code> ，则可以将其分成两个子字符串 <code>x</code> 和 <code>y</code> ，且满足 <code>s = x + y</code> 。</li>
<li><strong>随机</strong> 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，<code>s</code> 可能是 <code>s = x + y</code> 或者 <code>s = y + x</code> 。</li>
<li>在 <code>x</code> 和 <code>y</code> 这两个子字符串上继续从步骤 1 开始递归执行此算法。</li>
</ul>
</li>
</ol>
<p>给你两个 <strong>长度相等</strong> 的字符串 <code>s1</code><em> </em>和 <code>s2</code>，判断 <code>s2</code><em> </em>是否是 <code>s1</code><em> </em>的扰乱字符串。如果是，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>
<p> </p>
<p><strong>示例 1：</strong></p>
<pre>
<strong>输入：</strong>s1 = "great", s2 = "rgeat"
<strong>输出：</strong>true
<strong>解释：</strong>s1 上可能发生的一种情形是：
"great" --> "gr/eat" // 在一个随机下标处分割得到两个子字符串
"gr/eat" --> "gr/eat" // 随机决定：「保持这两个子字符串的顺序不变」
"gr/eat" --> "g/r / e/at" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割
"g/r / e/at" --> "r/g / e/at" // 随机决定：第一组「交换两个子字符串」，第二组「保持这两个子字符串的顺序不变」
"r/g / e/at" --> "r/g / e/ a/t" // 继续递归执行此算法，将 "at" 分割得到 "a/t"
"r/g / e/ a/t" --> "r/g / e/ a/t" // 随机决定：「保持这两个子字符串的顺序不变」
算法终止，结果字符串和 s2 相同，都是 "rgeat"
这是一种能够扰乱 s1 得到 s2 的情形，可以认为 s2 是 s1 的扰乱字符串，返回 true
</pre>
<p><strong>示例 2：</strong></p>
<pre>
<strong>输入：</strong>s1 = "abcde", s2 = "caebd"
<strong>输出：</strong>false
</pre>
<p><strong>示例 3：</strong></p>
<pre>
<strong>输入：</strong>s1 = "a", s2 = "a"
<strong>输出：</strong>true
</pre>
<p> </p>
<p><strong>提示：</strong></p>
<ul>
<li><code>s1.length == s2.length</code></li>
<li><code>1 <= s1.length <= 30</code></li>
<li><code>s1</code> 和 <code>s2</code> 由小写英文字母组成</li>
</ul>
---
[提交记录](https://leetcode.cn/problems/scramble-string/submissions/) | [题解](https://leetcode.cn/problems/scramble-string/solution/)
Solutions & Notes
properties:
note.updated:
displayName: Last Updated
note.relative_links:
displayName: Related Links
note.desc:
displayName: Description
note.grade:
displayName: Rating
note.program_language:
displayName: Language
note.time_complexity:
displayName: TC
note.space_complexity:
displayName: SC
views:
- type: table
name: Solutions & Notes
filters:
and:
- file.hasLink(this.file)
- file.tags.containsAny("leetcode/solution", "leetcode/note")
order:
- file.name
- desc
- program_language
- time_complexity
- space_complexity
- grade
- relative_links
- updated
sort:
- property: grade
direction: ASC
- property: time_complexity
direction: ASC
- property: program_language
direction: ASC
columnSize:
file.name: 104
note.space_complexity: 65
note.grade: 126
Similar Problems
properties:
note.lcTopics:
displayName: Topics
note.lcAcRate:
displayName: AC Rate
note.favorites:
displayName: Favorites
note.grade:
displayName: Rating
note.translatedTitle:
displayName: Title (CN)
note.lcDifficulty:
displayName: Difficulty
views:
- type: table
name: Similar Problems
filters:
and:
- file.hasLink(this.file)
- similarQuestions.contains(this.file)
order:
- file.name
- translatedTitle
- lcTopics
- lcDifficulty
- lcAcRate
- grade
- favorites
sort:
- property: file.name
direction: ASC
- property: lcTopics
direction: DESC
columnSize:
note.translatedTitle: 240
note.lcTopics: 347
note.lcAcRate: 75
note.grade: 122