Show problems as
Classic problem #87HardStringDynamic Programming

Scramble String

Real-world version: Folding A Part Code
Tracked in this browser only
Read Scramble String on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A press folds a part code by this rule.

  • A code of one character is left alone.
  • A code of two or more characters is cut at one position into two pieces, with neither piece empty. Each of the two pieces is then folded by this same rule. The two folded pieces are finally written down side by side, either in the order they were cut or with the second piece written first.

The press is free to cut wherever it likes and to choose either order, and it makes those two choices again for every piece it folds.

Given source and target, return true when the press can fold source into target, and false when it cannot. Folding never changes how many characters a code has, and the two given codes need not be the same length.

Examples

Example 1

Input
source = "cargo", target = "gorac"
Output
true

Cut `cargo` into `ca` and `rgo`. Folding `ca` and writing its two characters the other way round gives `ac`. Cutting `rgo` into `r` and `go` and writing the second piece first gives `gor`. Writing those two folded pieces with the second first gives `gor` then `ac`, which is `gorac`.

Example 2

Input
source = "swift", target = "sitwf"
Output
false

The two codes are built from the same five characters, but no set of cuts and orders folds the first into the second.

Example 3

Input
source = "weld", target = "welds"
Output
false

Folding leaves the number of characters unchanged, so a code of four characters can never be folded into a code of five.

Constraints

  • 1 <= source.length <= 30
  • 1 <= target.length <= 30
  • source and target consist of lowercase English letters.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def is_fold(source: str, target: str) -> bool:
Java
public boolean isFold(String source, String target)

More on the same topics