Shuffle by Cutting and Swapping

Hard

A string is shuffled like this: - if it has one character, nothing happens; - otherwise it is cut at any point into two non-empty pieces x and y (so the string is x + y), the pieces are optionally swapped (giving y + x), and then each piece is shuffled the same way on its own. You get two strings start and goal of equal length. Return true if some choice of cuts and swaps turns start into goal, and false otherwise.

Example 1

start="stone", goal="tones" → True

Cut "stone" into "s" and "tone" and swap them: "tone" + "s" = "tones". The pieces can then be left untouched.

Example 2

start="abcd", goal="bdac" → False

The first cut gives "a"+"bcd", "ab"+"cd" or "abc"+"d". To reach "bdac", one piece must hold the same letters as a prefix or suffix of "bdac" of the same length ("b", "bd", "bda" or "c", "ac", "dac"). None of them match, so the answer is false.

Example 3

start="z", goal="z" → True

Constraints

1 ≤ len(start) ≤ 30
len(goal) = len(start)
Both strings consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Does the Text Fit the Pattern Hard Ways to Cross Out Hard Fewest Cuts Into Palindromes Hard

Input

start="stone", goal="tones"

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 100 tests on the server, hidden ones included.