Why it works
- The last letter of a weave of i letters of a and j letters of b is a[i - 1] or b[j - 1]. So (i, j) can be built exactly when (i - 1, j) can and a[i - 1] is that letter of c, or (i, j - 1) can and b[j - 1] is.
- The table keeps every way at once. Taking c’s first a from a looks fine, but (1, 1) is false: c then needs c, and neither string offers it. The other choice, (0, 1), carries on to the end.
- Each cell reads only the cell above and the one to the left, both already filled in row-by-row order, so the bottom-right cell answers for the whole strings.
Complexity
Time O(n × m) for a and b of lengths n and m: one cell per pair of prefixes, each checked in constant time. Memory O(n × m) for the table; one row updated in place is enough, O(m).
nextNow solve it yourself, no hints.
Solve on LeetCode ↗