Weaving Two Strings

Medium

You are given three strings left, right and woven. Check whether woven can be produced by weaving left and right together: repeatedly take the next unused letter from one string or the other. The letters of left keep their order, as do the letters of right; every letter of both is used exactly once, and woven contains nothing else. You may take as many letters in a row from one string as you like. Return True if such a weaving exists and False otherwise. Bonus: can you do it with O(len(right)) extra memory?

Example 1

left="tea", right="pot", woven="tpeoat" → True

The letters of woven come alternately from left and right: t(left) p(right) e(left) o(right) a(left) t(right).

Example 2

left="ab", right="ba", woven="aabb" → False

The first letter of woven is a, which only left can supply. The next letter must be a again, but the next available letters are b from left and b from right. No weaving works.

Example 3

left="", right="xyz", woven="xyz" → True

Constraints

0 ≤ len(left), len(right) ≤ 100
0 ≤ len(woven) ≤ 200
All 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

Longest Mirror Fragment Medium All Balanced Bracket Strings Medium Fewest Letter Edits Medium Ways to Read a Digit Code Medium Cutting a Word Into Palindromes Medium

Input

left="tea", right="pot", woven="tpeoat"

Expected

True

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