Can a signal tape be split into known patterns?

Question

A recorded "tape" is one long string. You have a dictionary of valid motifs (short strings). Decide whether the whole tape can be cut into a sequence of motifs back-to-back, using each motif as many times as you like.

tape = "upupdn", motifs = ["up", "dn", "updn"]
-> True     # "up" + "up" + "dn"  (also "up" + "updn")

Return whether the tape splits exactly into dictionary motifs (word break).

Accepted Answer

Let dp[i] mean "the first i characters can be fully segmented." Start with dp[0] = True (the empty prefix). For each end position i, look for a cut point j such that the prefix up to j is already segmentable (dp[j]) and the piece tape[j:i] is a valid motif. A set makes the membership test O(1). Tracing "upupdn": dp[2], dp[4], and dp[6] become True (after "up", "upup", and the full "upupdn"), so the answer is True. Time O(n^2) substring checks (O(n^2 L) if you count slicing), space O(n). Edge cases: an empty tape is trivially segmentable (True); if no motif matches a needed piece, dp[n] stays …

Can a signal tape be split into known patterns?

Your answer

More Coding questions