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

Problem Description

The challenge is to find out if a given searchWord is a prefix of any word in the sentence. The sentence is a string made up of words separated by single spaces. A prefix is defined as the initial part of a word. If the searchWord is found to be the prefix of one or more words in the sentence, we need to return the position of the first word (with the smallest index) where the searchWord is a prefix. Otherwise, we return -1. The words in the sentence are 1-indexed, meaning the first word is considered to be at position 1, the second word at position 2, and so on.

Intuition

The intuitive approach to solve this problem involves checking each word in the given sentence to see if it starts with the searchWord. We split the sentence into individual words and iterate over them. With each iteration, we check whether the current word begins with the searchWord using the startswith() method. If we find a match, we return the current index, which corresponds to the position of the word in the sentence. If we finish iterating over all the words without finding a match, we return -1 as per the problem's requirement. The enumerate() function coupled with a starting index of 1 is used to keep track of the word positions in a 1-indexed fashion.

Solution Approach

The solution uses a simple linear scan algorithm to solve the problem, which is efficient considering the problem's constraints. Since the sentence is guaranteed to have words separated by a single space, we can directly use the split() function in Python, which, by default, splits the string by any whitespace, including spaces. This provides us with a list of words contained in the sentence.

With the list obtained, we proceed with the enumerate() function, which iterates over the list and provides both the index and value of each item. However, to maintain the 1-indexed requirement, we start the enumeration from 1 by passing 1 as the second argument to enumerate().

During each iteration, we check for the prefix condition using the startswith() method, which is a string method in Python that returns True if the string starts with the specified prefix, False otherwise.

The loop iterates through all words in the sentence. If a word is found that starts with searchWord, the loop breaks, and the current index is returned. This index corresponds to the word's 1-indexed position in the original sentence. If no such word is found and the loop finishes, the function returns -1 to indicate the absence of a valid prefix match.

Here's the specific implementation from the provided code:

1class Solution:
2    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
3        # Split sentence into words and enumerate them starting from 1
4        for i, word in enumerate(sentence.split(), 1):
5            # Check if current word starts with searchWord
6            if word.startswith(searchWord):
7                return i  # Return the 1-index position of the word
8        return -1  # Return -1 if no prefix match is found in any words

No additional data structures are used, and the startswith() method provides a clean and readable way to check the prefix condition, making this solution straightforward and easy to understand.

Example Walkthrough

Let's take the sentence "hello world hi hey" and the searchWord "he". We want to find out if "he" is a prefix of any word in the sentence and return the position of the first word where "he" is a prefix.

The solution approach is as follows:

1. The sentence is split into individual words, giving us a list ["hello", "world", "hi", "hey"].

2. We use enumerate() to iterate over this list, starting indexing at 1 to match the problem's 1-indexed word position requirement.

3. For each word, we check if the searchWord "he" is a prefix of the word using the startswith() method.

4. We start with the first word "hello":

   • "hello".startswith("he") is True.
   • Since this condition is true, and "hello" is the first word, we return its 1-index position, which is 1.

Therefore, in this example, the searchWord "he" is a prefix of the word "hello", and the position returned is 1.

If the searchWord was "hi" instead, the steps would be followed until we reached the word "hi":

1. "hello".startswith("hi") is False.
2. "world".startswith("hi") is False.
3. "hi".startswith("hi") is True, so we would return the 1-index position, which is 3 in this case.

And if our searchWord was something like "xyz", which isn't a prefix for any of the words:

1. "hello".startswith("xyz") is False.
2. "world".startswith("xyz") is False.
3. "hi".startswith("xyz") is False.
4. "hey".startswith("xyz") is False.
   • Since no words start with "xyz", we reach the end of the iteration and return -1.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n * k) where n is the number of words in the sentence and k is the length of searchWord. This is because:

• The split() method is called on the sentence, which takes O(m) time, where m is the length of the sentence.
• Every word is compared with searchWord using startswith(), which in the worst case checks up to k characters for each of the n words.

Space Complexity

The space complexity of the given code is O(n) where n is the number of words in the sentence. This is due to:

• The split() method, which creates a list of words from the sentence, storing each word as a separate element in the list. In the worst case, the list will contain n elements, thus taking O(n) space.

Learn more about how to find time and space complexity quickly using problem constraints.