Skip to main content
Talentd

Check If a Word Occurs As a Prefix of Any Word in a Sentence - Solution & Explanation

EasyTwo PointersStringString Matching15 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

Given a sentence that consists of some words separated by a single space, and a searchWord, check if searchWord is a prefix of any word in sentence.

Return the index of the word in sentence (1-indexed) where searchWord is a prefix of this word. If searchWord is a prefix of more than one word, return the index of the first word (minimum index). If there is no such word return -1.

A prefix of a string s is any leading contiguous substring of s.

 

Example 1:

Input: sentence = "i love eating burger", searchWord = "burg"
Output: 4
Explanation: "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
Explanation: "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
Explanation: "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.

Approach Overview

Problem Overview: Given a sentence containing words separated by spaces and a searchWord, return the 1-indexed position of the first word where searchWord appears as its prefix. If no word starts with that prefix, return -1.

Approach 1: Split and Compare using Simple Loop (Time: O(n * k), Space: O(n))

Split the sentence into individual words using the space delimiter, then iterate through the resulting array. For each word, check whether its first k characters match searchWord where k = searchWord.length. Most languages provide built-in helpers like startsWith or substring comparison, which keeps the implementation short and readable. This approach relies entirely on basic string operations and works well when clarity is more important than minimizing auxiliary memory.

Approach 2: Two-Pointer Traversal (Time: O(n), Space: O(1))

Instead of splitting the sentence, scan the string directly using two pointers. One pointer walks through the sentence character by character while another checks characters against searchWord when the start of a word is detected. A word boundary occurs at index 0 or immediately after a space. From each boundary, compare characters sequentially until either the prefix fully matches or a mismatch occurs. This avoids allocating an array of words and performs a single pass through the sentence. The technique is a practical use of two pointers combined with lightweight string matching.

Recommended for interviews: Both approaches are acceptable because the constraints are small and the logic is straightforward. Starting with the split-based loop demonstrates clear reasoning and correctness. The two-pointer traversal shows stronger control over string processing and space optimization, which interviewers often appreciate when discussing performance tradeoffs.

Approach 1: Split and Compare using Simple Loop

This method involves splitting the input sentence into words and then iterating through each word to check if the searchWord is a prefix of that word. If a match is found, the index of the word (1-based) is returned. If no match is found, -1 is returned.

Using strtok to split the sentence into words. For each word, strncmp checks if the searchWord is a prefix. The index is returned if found; otherwise, it continues. If no prefix is found, -1 is returned.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m) where n is the number of words and m is the average length of words.
Space Complexity: O(1).

Try this approach in the editor →

Approach 2: Two-Pointer Traversal

This approach uses a two-pointer technique to traverse the sentence and words simultaneously for efficient prefix checking. It doesn't rely on splitting the string into words but rather navigates the sentence using custom logic.

Utilizes two pointers: i for traversing the sentence and j for the searchWord. Iterates character by character to check prefix while tracking spaces to identify words and reset checks.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the length of the sentence, as it efficiently traverses the string.
Space Complexity: O(1) as only pointers are used.

Try this approach in the editor →

Approach 3: String Splitting

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

The time complexity is O(m times n), and the space complexity is O(m). Here, m and n are the lengths of sentence and searchWord, respectively.

Code

PythonJavaC++GoTypeScriptRustPHP

Python

Java

C++

Go

TypeScript

Rust

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Split and Compare using Simple Loop

Time Complexity: O(n * m) where n is the number of words and m is the average length of words.
Space Complexity: O(1).

Two-Pointer Traversal

Time Complexity: O(n) where n is the length of the sentence, as it efficiently traverses the string.
Space Complexity: O(1) as only pointers are used.

String Splitting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Split and Compare using Simple LoopO(n * k)O(n)When readability matters and using built-in string helpers like startsWith is acceptable.
Two-Pointer TraversalO(n)O(1)When you want a single-pass scan without allocating extra memory for split words.

Video Solution

Check if a Word Occurs As a Prefix of Any Word in a Sentence | Leetcode 1455 • Technosage • 8,472 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Check If a Word Occurs As a Prefix of Any Word in a Sentence easy or hard?
LeetCode classifies this problem as Easy with an acceptance rate around 68%. The logic involves basic string iteration and prefix comparison, making it suitable for beginners practicing string manipulation and simple two-pointer techniques.
Check If a Word Occurs As a Prefix of Any Word in a Sentence Python/Java solution
In Python or Java, iterate through each word and check if it starts with searchWord using built-in methods like startswith or startsWith. Return the 1-indexed position of the first matching word, otherwise return -1. A more optimized implementation scans the sentence directly using two pointers for O(1) space.
How to solve Check If a Word Occurs As a Prefix of Any Word in a Sentence in O(n)?
Traverse the sentence once while tracking word boundaries. When you encounter the start of a word (index 0 or after a space), compare characters sequentially with searchWord. If all characters match, return the word index. Because each character in the sentence is processed at most once, the total runtime remains O(n).
What is the best approach for Check If a Word Occurs As a Prefix of Any Word in a Sentence?
The most practical approach is scanning the sentence and checking each word's prefix. A two-pointer traversal achieves this in O(n) time and O(1) space by detecting word boundaries and matching characters with searchWord. A simpler alternative is splitting the sentence into words and using a startsWith comparison.
Is Check If a Word Occurs As a Prefix of Any Word in a Sentence asked at Google/Amazon/Meta?
Prefix and string scanning problems appear frequently in interviews at companies like Amazon, Google, and Meta, especially in easy or warm-up rounds. This problem tests understanding of string traversal, prefix matching, and careful handling of word boundaries.
What data structure is used in Check If a Word Occurs As a Prefix of Any Word in a Sentence?
The problem primarily uses basic string processing. The split-based solution temporarily stores words in an array, while the optimal approach uses two pointers directly on the input string without additional data structures.
What is the time complexity of Check If a Word Occurs As a Prefix of Any Word in a Sentence?
The typical solution runs in O(n) to O(n * k) time where n is the sentence length and k is the length of searchWord. Each word is checked only until the prefix either matches or fails. Space complexity is O(1) with a pointer scan or O(n) if the sentence is split into an array of words.

Ready to solve this problem?

Practice Check If a Word Occurs As a Prefix of Any Word in a Sentence with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Prefixes of a Given String

Next

Counting Words With a Given Prefix