Check If a Word Occurs As a Prefix of Any Word in a Sentence
EasyPrompt
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 <= 10sentenceconsists of lowercase English letters and spaces.searchWordconsists of lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This is the most straightforward approach. We first split the input sentence into an array of individual words using the space character as a delimiter. Then, we iterate through this array of words. For each word, we use the built-in startsWith() method to check if it begins with the searchWord. If a match is found, we return the current word's index (1-based). If we iterate through all the words without finding a prefix match, we return -1.
Algorithm
- Use the
split(" ")method on thesentencestring to get an array of words. - Loop through the
wordsarray from indexi = 0towords.length - 1. - Inside the loop, check if
words[i].startsWith(searchWord). - If the condition is true, it means we've found the first word that has
searchWordas a prefix. Returni + 1since the problem asks for a 1-indexed result. - If the loop completes without finding any match, return -1.
Walkthrough
This method relies on built-in string manipulation functions to simplify the logic. First, the sentence is broken down into a list of words. Then, we check each word in sequence for the required prefix. The first match found is the one we need, so we can return its index immediately.
class Solution { public int isPrefixOfWord(String sentence, String searchWord) { String[] words = sentence.split(" "); for (int i = 0; i < words.length; i++) { if (words[i].startsWith(searchWord)) { return i + 1; // 1-indexed result } } return -1; }}Complexity
Time
O(N + W*M), where `N` is the length of the `sentence`, `W` is the number of words, and `M` is the length of the `searchWord`. The `split()` operation takes `O(N)` time. The loop runs `W` times, and inside the loop, `startsWith()` takes `O(M)` time in the worst case.
Space
O(N), where `N` is the length of the `sentence`. The `split()` method creates a new array of strings, and the total size of these strings is proportional to the length of the original sentence `N`.
Trade-offs
Pros
Simple and easy to understand and implement.
Leverages built-in, highly-optimized library functions.
Cons
Uses extra space to store the array of words, which can be inefficient for very long sentences.
Solutions
Solution
class Solution {public int isPrefixOfWord(String sentence, String searchWord) { String[] words = sentence.split(" "); for (int i = 0; i < words.length; ++i) { if (words[i].startsWith(searchWord)) { return i + 1; } } return -1; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.