/87. Scramble String

87. Scramble String

Hard
Strings44.1% acceptance

Given two strings source and target of equal length, determine if target can be obtained from source by recursively splitting source into two non-empty substrings, optionally swapping them, and applying the same process to each substring. Return True if target can be obtained from source using this process, otherwise return False.

Example 1

Input: source = listen, target = silent

Output: False

Explanation: Although silent is an anagram of listen, it cannot be obtained by the allowed scrambling process.

Example 2

Input: source = aabb, target = abab

Output: True

Explanation: By splitting and swapping, abab can be obtained from aabb.

Example 3

Input: source = xy, target = yx

Output: True

Explanation: Splitting at index 1 and swapping yields yx.

Constraints

  • 1 <= len(source) <= 30
  • len(source) == len(target)
  • source and target consist of lowercase English letters
Python (current runtime)

Case 1

Input: source = 'abcdef', target = 'badcfe'

Expected: False

Case 2

Input: source = 'abc', target = 'bca'

Expected: True

Case 3

Input: source = 'aa', target = 'aa'

Expected: True

Case 4

Input: source = 'abcd', target = 'cdab'

Expected: True

Case 5

Input: source = 'abcd', target = 'acbd'

Expected: False