803. Interleaved Weave
A weaver owns two threads whose colour patterns are the lowercase strings a and b. To make a cloth she repeatedly takes the next unused stitch from the front of either thread and appends it to the cloth, until both threads are used up. The order of stitches inside each thread never changes.
Given a cloth pattern c, return true if the weaver can produce exactly c this way, and false otherwise. If the lengths of a and b do not add up to the length of c, the answer is false.
Aim for O(n*m) time, where n and m are the lengths of a and b, and O(m) extra space.
Example 1
- Input:
- a = "tom", b = "jerry", c = "tjoemrry"
- Output:
- true
- Explanation:
The pattern "tjoemrry" can be woven from "tom" and "jerry" while keeping the order inside each thread.
Example 2
- Input:
- a = "sun", b = "moon", c = "sumoonn"
- Output:
- true
- Explanation:
The pattern "sumoonn" can be woven from "sun" and "moon" while keeping the order inside each thread.
Example 3
- Input:
- a = "kay", b = "kay", c = "kkaayy"
- Output:
- true
- Explanation:
The pattern "kkaayy" can be woven from "kay" and "kay" while keeping the order inside each thread.
Constraints
1 ≤ a.length, b.length ≤ 1000, 1 ≤ c.length ≤ 2000
All strings contain only lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n*m)
- Space
- O(m)