Two people type messages a and b into the same chat box at the same time, and their keystrokes get mixed together into c. Every character of a and of b ends up in c exactly once, and each person's characters keep their own order, but the two streams can alternate in any way.
Write is_weave(a: str, b: str, c: str) -> bool that returns True if c could have been produced this way from a and b.
is_weave("abc", "xy", "axbyc") # True
is_weave("ab", "cd", "cadb") # True c(b) a(a) d(b) b(a)
is_weave("ab", "cd", "badc") # False "b" can't come before "a"
is_weave("aab", "aac", "aacaab") # True
is_weave("ab", "c", "abcd") # False lengths don't add up
is_weave("", "", "") # True
Constraints:
0 <= len(a), len(b) <= 1000,0 <= len(c) <= 2000- all strings contain only lowercase English letters
When both a and b could supply the next character, you can't tell which is right, and exploring both branches blindly takes exponential time. Aim for O(len(a) · len(b)) time.
Show hint
after using the first i characters of a and the first j of b, you have produced exactly the first i + j characters of c. Whether you can finish depends only on the pair (i, j).