Watch 10 video solutions for Check If a Word Occurs As a Prefix of Any Word in a Sentence, a easy level problem involving Two Pointers, String, String Matching. This walkthrough by Technosage has 7,888 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1001 <= searchWord.length <= 10sentence consists of lowercase English letters and spaces.searchWord consists of lowercase English letters.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 | Time | Space | When to Use |
|---|---|---|---|
| Split and Compare using Simple Loop | O(n * k) | O(n) | When readability matters and using built-in string helpers like startsWith is acceptable. |
| Two-Pointer Traversal | O(n) | O(1) | When you want a single-pass scan without allocating extra memory for split words. |