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

Easy

#1344Time: 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`.1 company

Patterns

Two Pointers String Matching

Data structures

String

Companies

Yelp

Prompt

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.

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 the sentence string to get an array of words.
Loop through the words array from index i = 0 to words.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 searchWord as a prefix. Return i + 1 since 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.

1class Solution {2    public int isPrefixOfWord(String sentence, String searchWord) {3        String[] words = sentence.split(" ");4        for (int i = 0; i < words.length; i++) {5            if (words[i].startsWith(searchWord)) {6                return i + 1; // 1-indexed result7            }8        }9        return -1;10    }11}

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.

This approach improves upon the first one by avoiding the creation of an intermediate array of words, thus reducing the space complexity to be constant. We can iterate through the sentence character by character, keeping track of the current word index. When we detect the beginning of a new word (either at the start of the sentence or after a space), we check if that word starts with the searchWord.

Algorithm

Initialize a wordIndex counter to 1.
Iterate through the sentence string with an index i from 0 to the end.
At each character, check if it marks the beginning of a word. A character at index i is the start of a word if i is 0, or if the character at i-1 is a space.
If it is the start of a word, use a function like sentence.startsWith(searchWord, i) to check for a prefix match starting from the current position i.
If a match is found, return the current wordIndex.
If the character at index i is a space, it signifies the end of the current word, so we increment wordIndex.
If the loop finishes without returning, it means no match was found. Return -1.

Walkthrough

By manually parsing the string, we can avoid the overhead of creating a new array of strings. We iterate through the sentence, and every time we encounter the beginning of a word, we perform the prefix check. The beginning of a word is identified as either the very first character of the sentence or a character that immediately follows a space. We also keep a counter for the word index, which is incremented every time we pass a space.

1class Solution {2    public int isPrefixOfWord(String sentence, String searchWord) {3        int n = sentence.length();4        int wordIndex = 1;5        for (int i = 0; i < n; ++i) {6            // Check if it's the start of a word7            if (i == 0 || sentence.charAt(i - 1) == ' ') {8                // Use the built-in startsWith with an offset9                if (sentence.startsWith(searchWord, i)) {10                    return wordIndex;11                }12            }13            // Increment word index when a space is encountered14            if (sentence.charAt(i) == ' ') {15                wordIndex++;16            }17        }18        return -1;19    }20}

Complexity

Time

O(N * M), where `N` is the length of the `sentence` and `M` is the length of `searchWord`. We iterate through the sentence once (`O(N)`). At the beginning of each word, we perform a `startsWith` check which can take up to `O(M)` time. This gives a worst-case complexity of `O(N*M)`.

Space

O(1). This approach uses only a few variables to keep track of the state (`i`, `wordIndex`), and does not create any data structures whose size depends on the input length.

Trade-offs

Pros

Highly space-efficient (O(1) space).
Processes the sentence in a single pass without creating intermediate data structures.

Cons

The logic can be slightly more complex to write and reason about compared to the split() approach.

Solutions

Solution

1class Solution {2public3  int isPrefixOfWord(String sentence, String searchWord) {4    String[] words = sentence.split(" ");5    for (int i = 0; i < words.length; ++i) {6      if (words[i].startsWith(searchWord)) {7        return i + 1;8      }9    }10    return -1;11  }12}

1class Solution {2public:3  int isPrefixOfWord(string sentence, string searchWord) {4    stringstream ss(sentence);5    string s;6    for (int i = 1; ss >> s; ++i) {7      if (s.find(searchWord) == 0) {8        return i;9      }10    }11    return -1;12  }13};

1class Solution:2    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int: for i, s in enumerate(sentence . split(), 1): if s . startswith(searchWord): return i 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.

← Previous

Previous problem

Next problem