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.

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.

Description Hints 3 Solution Video 6:11

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

Q: 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.

Q: 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).

Easy68.8% acceptance4 companies

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.

Asked at 4 companies

Yelp

Google Amazon Microsoft

Topics

Hints open one at a time

Hint 1

First extract the words of the sentence.

Hint 2

Check for each word if searchWord occurs at index 0, if so return the index of this word (1-indexed)

Hint 3

If searchWord doesn't exist as a prefix of any word return the default value (-1).

6:11

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution