#1455

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Check If a Word Occurs As a Prefix of Any Word in a Sentence

Determine the first word in a sentence where a given searchWord is a prefix using two-pointer scanning with string matching.

two pointers string string matching

Problem Statement

Given a sentence consisting of lowercase words separated by single spaces and a searchWord, determine whether searchWord is a prefix of any word in the sentence. Return the 1-based index of the first word where searchWord is a prefix. If no word matches, return -1. Each prefix comparison should only check the starting characters to optimize scanning.

A prefix of a string is defined as any contiguous substring that starts at the beginning of that string. For example, 'pro' is a prefix of 'problem', but not of 'apple'. Ensure that if multiple words match, only the minimal index is returned.

Examples

Example 1

Input: sentence = "i love eating burger", searchWord = "burg"

Output: 4

"burg" is prefix of "burger" which is the 4th word in the sentence.

Example 2

Input: sentence = "this problem is an easy problem", searchWord = "pro"

Output: 2

"pro" is prefix of "problem" which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.

Example 3

Input: sentence = "i am tired", searchWord = "you"

Output: -1

"you" is not a prefix of any word in the sentence.

Constraints

1 <= sentence.length <= 100
1 <= searchWord.length <= 10
sentence consists of lowercase English letters and spaces.
searchWord consists of lowercase English letters.

Solution Approach

Extract Words Using Two Pointers

Use a left and right pointer to scan the sentence. Move the right pointer until a space or the end of the string is reached, forming a word. This ensures each word is checked without extra splitting overhead.

Compare Prefix Efficiently

For each extracted word, compare its first k characters with the searchWord length k. If they match, immediately return the current 1-based index. This avoids unnecessary full string comparisons and follows the two-pointer invariant.

Return Default if No Match

If the end of the sentence is reached without finding any prefix match, return -1. This handles edge cases like empty searchWord or non-matching sentences, preserving the O(n) time and O(n) space bounds.

Complexity Analysis

Metric	Value
Time	O(n + m) \approx O(n)
Space	O(n)

Time complexity is O(n + m) where n is the sentence length and m is the searchWord length, since each character is visited once in two-pointer scanning. Space complexity is O(n) for storing words or temporary slices during scanning, ensuring linear memory usage.

What Interviewers Usually Probe

Candidate attempts direct string splitting instead of incremental scanning.
Candidate compares full words instead of only prefix length.
Candidate misses 1-based indexing requirement for the returned word.

Common Pitfalls or Variants

Common pitfalls

Checking all characters of each word instead of only the prefix length.
Returning index of last matching word instead of first minimal index.
Ignoring edge cases where searchWord does not match any word, causing incorrect defaults.

Follow-up variants

Return all indices of words where searchWord is a prefix, instead of first match.
Allow uppercase letters and ignore case during prefix comparison.
Find the longest matching prefix instead of the first word match.

FAQ

What pattern does this problem follow?

This problem uses the two-pointer scanning with invariant tracking pattern, focusing on efficient prefix detection within a sentence.

How do I handle multiple words matching the prefix?

Return only the 1-based index of the first word that matches the searchWord prefix to satisfy minimal index requirement.

Can I use built-in split functions?

Yes, but using two-pointer scanning reduces extra memory allocation and aligns with the two-pointer invariant approach.

What is the expected time complexity?

The solution should run in O(n + m) time where n is sentence length and m is searchWord length, scanning each character once.

How to implement prefix comparison correctly?

Compare only the first k characters of each word with the searchWord of length k to efficiently detect prefix matches without extra checks.

terminal

Solution

Solution 1: String Splitting

We split $\textit{sentence}$ by spaces into $\textit{words}$, then iterate through $\textit{words}$ to check if $\textit{words}[i]$ is a prefix of $\textit{searchWord}$. If it is, we return $i+1$. If the iteration completes and no words satisfy the condition, we return $-1$.

1

2

3

4

5

6

class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        for i, s in enumerate(sentence.split(), 1):
            if s.startswith(searchWord):
                return i
        return -1

Continue Practicing

#1023 camelcase matching #1408 string matching in an array #1397 find all good strings