A weaver has two threads, left and right, each a string of colour letters. Weaving pulls one letter at a time from the front of either thread and appends it to the cloth. Given the finished cloth, return True if it can be produced from the two threads (using all of both), otherwise False.
Examples
Input: left = "rope", right = "knot", cloth = "rkonpoet"
Output: True
Explanation: r k o n p o e t alternates left, right, left, right, ...
Input: left = "abc", right = "xyz", cloth = "axbzyc"
Output: False
Explanation: after "axb" the next letter must be c or y, not z.
Constraints
0 <= len(left), len(right) <= 150,0 <= len(cloth) <= 300- Lowercase letters only.
- Target complexity: O(len(left) * len(right)). Trying every way to pick threads is exponential.
Goals
- Use a boolean table indexed by how much of each source string is consumed
- Check the length condition before doing any DP work