Show problems as
Classic problem #97MediumStringDynamic Programming

Interleaving String

Real-world version: Merged Two Feed Lanes
Tracked in this browser only
Read Interleaving String on LeetCode(opens in a new tab)

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

Two feed lanes discharge onto a single packing belt. Each lane holds a queue of parts written as a string of lowercase letters, one letter per part: left is the left lane and right the right lane, and the first letter of each is the part at the head of that lane.

An operator clears both lanes onto the belt one part at a time. At every step they pick a lane that still has parts and release the part at its head. Nothing is skipped, nothing is added, and neither lane may be reordered, so the parts of a single lane arrive on the belt in the order they were queued.

belt is the run that came off the belt, head part first. Return true when some sequence of lane picks produces exactly belt, and false otherwise.

Examples

Example 1

Input
left = "ab", right = "cd", belt = "acbd"
Output
true

Releasing a from the left lane, then c from the right, then b from the left, then d from the right lays down a, c, b, d. Within each lane the parts came off in their queued order.

Example 2

Input
left = "ab", right = "cd", belt = "abdc"
Output
false

The belt carries all four parts, but d comes off before c while the right lane queues c ahead of d, so no run of picks can produce it.

Example 3

Input
left = "", right = "xy", belt = "xy"
Output
true

The left lane is empty, so every pick comes from the right lane and the belt shows that lane's own order.

Constraints

  • 0 <= left.length, right.length <= 100
  • 0 <= belt.length <= 200
  • left, right, and belt 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_merge(left: str, right: str, belt: str) -> bool:
Java
public boolean isMerge(String left, String right, String belt)

More on the same topics