One Insertion to Match

Medium

You are given two sentences one and two. Each is a list of words made of English letters, separated by single spaces, with no leading or trailing spaces. Can you insert some whole words (possibly none) into **one** spot of one of the sentences so that the two become identical? The spot may be the start, the end or a gap between two words, but never the inside of a word. For example, "Good day" becomes "Good sunny day", but "Sun day" cannot become "Sunny day": the inserted "ny" is not separated by a space. Return True if it is possible, otherwise False. Letter case matters.

Example 1

one="Meet me at the gate", two="Meet me gate" → True

Inserting "at the" between "me" and "gate" in the second sentence turns it into the first.

Example 2

one="red car", two="red fast car now" → False

The missing words sit in two different places ("fast" and "now"), but only one insertion is allowed.

Example 3

one="Hat", two="hat" → False

Case matters: "Hat" and "hat" are different words.

Constraints

1 ≤ len(one), len(two) ≤ 10⁵
Sentences consist of uppercase and lowercase English letters with single spaces between words

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers String

Similar problems

A Subsequence of One Word Only Medium Longest Word by Crossing Out Medium Words With Drawn-Out Letters Medium Capitals Follow the Pattern Medium Word Growth Chain Medium

Input

one="Meet me at the gate", two="Meet me gate"

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 198 tests on the server, hidden ones included.