Missing Words Sequence
EasyString · SalesForce
You are given two sentences, source and target. Words are separated by single spaces and compared exactly (case-sensitive).
target was produced by deleting zero or more words from source while keeping the remaining words in their original order, so the words of target form a subsequence of the words of source.
Return the list of deleted words in the order they appear in source.
When a word repeats, match each target word to the earliest unused occurrence in source (scan both sentences left to right). For example, with source = "a b a" and target = "a", the target word matches the first a, so the answer is ["b", "a"].
Example 1
- Input:
- source = "the quick brown fox jumps over the lazy dog", target = "quick fox over the dog"
- Output:
- ["the", "brown", "jumps", "lazy"]
- Explanation
- The first
theis skipped becausetargetstarts withquick. Thenbrownandjumpsare skipped, the secondthematches thetargetwordthe, andlazyis skipped.
Example 2
- Input:
- source = "to be or not to be", target = "to be"
- Output:
- ["or", "not", "to", "be"]
- Explanation
to bematches the first two words, so everything after them is reported as deleted, including the secondto be.
Example 3
- Input:
- source = "go go go", target = "go go go"
- Output:
- []
- Explanation
- Every word of
sourceis matched, so the answer is empty.
Constraints
- 0 ≤
source.length,target.length≤ 105 - Words contain printable non-space characters and are separated by single spaces
- The words of
targetare a subsequence of the words ofsource