Problem Description

You are given a sentence containing words separated by single spaces, and a searchWord. Your task is to find if searchWord appears as a prefix (beginning part) of any word in the sentence.

The problem asks you to:

• Check each word in the sentence to see if it starts with searchWord
• Return the position (1-indexed, meaning counting starts from 1) of the first word that has searchWord as its prefix
• If multiple words have searchWord as a prefix, return the smallest index (the first occurrence)
• If no word has searchWord as a prefix, return -1

For example:

• If sentence = "i love eating burger" and searchWord = "burg", the word "burger" (4th word) starts with "burg", so return 4
• If sentence = "this problem is an easy problem" and searchWord = "pro", the word "problem" appears twice (3rd and 6th positions), but we return 3 (the first occurrence)
• If no word starts with the search word, return -1

The solution splits the sentence into individual words using split(), then iterates through each word with its index (starting from 1). For each word, it checks if the word starts with searchWord using the startswith() method. As soon as a match is found, it returns the current index. If no match is found after checking all words, it returns -1.

Intuition

The key insight is that we need to check if searchWord is a prefix of any word in the sentence. A prefix means the word must start with exactly the characters in searchWord.

Since we need to find the position of words in the sentence, the natural approach is to break the sentence into individual words first. This way, we can examine each word separately and keep track of its position.

For checking if a word starts with searchWord, we can use string comparison. In Python, the startswith() method directly checks if a string begins with a given substring, making this check straightforward.

The requirement to return the first (minimum index) word that matches tells us we should process words in order from left to right. As soon as we find a match, we can immediately return that position without checking the remaining words. This gives us both correctness and efficiency.

The 1-indexed requirement means we need to adjust our counting - instead of starting from 0 (as is typical in programming), we start counting from 1. Python's enumerate() function conveniently allows us to specify a starting value of 1, handling this requirement elegantly.

The overall strategy becomes: split the sentence → iterate through words in order → check each word for the prefix → return immediately when found → return -1 if we finish checking all words without finding a match.

Learn more about Two Pointers patterns.

Solution Approach

The solution implements a straightforward linear search through the words of the sentence using string splitting.

Step 1: Split the sentence into words
We use sentence.split() to break the sentence into a list of individual words. The split() method with no arguments automatically splits on whitespace, which handles the single space separation mentioned in the problem.

Step 2: Iterate through words with their indices
We use enumerate(sentence.split(), 1) to iterate through the words. The enumerate() function provides both the index and the value for each word. The second parameter 1 tells enumerate to start counting from 1 instead of 0, which directly gives us the 1-indexed position required by the problem.

Step 3: Check prefix condition
For each word s at position i, we check if searchWord is a prefix using s.startswith(searchWord). This built-in method returns True if the word s begins with the exact characters in searchWord.

Step 4: Return result

• If we find a word that starts with searchWord, we immediately return its index i. Since we're iterating from left to right, the first match we find is automatically the minimum index.
• If the loop completes without finding any matching word, we return -1.

The time complexity is O(n * m) where n is the number of words in the sentence and m is the length of searchWord (for the prefix comparison). The space complexity is O(n) for storing the split words.

Example Walkthrough

Let's walk through the solution with the example: sentence = "i love eating burger" and searchWord = "burg"

Step 1: Split the sentence into words

sentence.split() → ["i", "love", "eating", "burger"]

Step 2: Iterate through words with their indices (starting from 1)

enumerate(["i", "love", "eating", "burger"], 1) gives us:
- (1, "i")
- (2, "love") 
- (3, "eating")
- (4, "burger")

Step 3: Check each word to see if it starts with "burg"

• Index 1: Does "i" start with "burg"? → No, continue
• Index 2: Does "love" start with "burg"? → No, continue
• Index 3: Does "eating" start with "burg"? → No, continue
• Index 4: Does "burger" start with "burg"? → Yes! Return 4

Result: The function returns 4 because "burger" is the 4th word and it starts with "burg".

Let's trace through another example where no match is found: sentence = "hello world" and searchWord = "foo"

• Index 1: Does "hello" start with "foo"? → No, continue
• Index 2: Does "world" start with "foo"? → No, continue
• Loop completes without finding a match → Return -1

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the length of sentence and n is the length of searchWord. This is because:

• sentence.split() takes O(m) time to traverse the entire sentence
• For each word in the sentence, startswith() performs character-by-character comparison with searchWord, which takes up to O(n) time
• In the worst case, we check all words in the sentence, each requiring O(n) comparison time

The space complexity is O(m). This is because:

• sentence.split() creates a list containing all words from the sentence, which requires O(m) space to store all the characters from the original sentence (distributed across multiple word strings)
• The iteration variables i and s use O(1) additional space
• No other data structures are created that scale with input size

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

Common Pitfalls

1. Case Sensitivity Mismatch The most common pitfall is not considering case sensitivity. The startswith() method is case-sensitive, so "Burger" won't match with "burg" as a prefix. If the problem doesn't explicitly state case-sensitive matching, this could lead to incorrect results.

Solution: If case-insensitive matching is needed, convert both strings to the same case:

if word.lower().startswith(searchWord.lower()):
    return index

2. Assuming searchWord is Shorter Than Words The code doesn't explicitly handle cases where searchWord might be longer than some words in the sentence. While startswith() handles this correctly (returning False), developers might make incorrect assumptions.

Example: If sentence = "a cat sat" and searchWord = "category", the word "cat" is shorter than "category" but the code handles it properly.

3. Multiple Spaces Between Words If the input has multiple spaces between words (e.g., "hello world"), split() without arguments handles this correctly by treating consecutive spaces as a single separator. However, using split(' ') with a single space argument would create empty strings in the list.

Solution: Always use split() without arguments for whitespace splitting:

# Good: handles multiple spaces
words = sentence.split()

# Bad: creates empty strings with multiple spaces
words = sentence.split(' ')  # ['hello', '', 'world']

4. Not Using Early Return Some implementations might store all matching indices and then return the minimum, which is inefficient:

# Inefficient approach
matches = []
for index, word in enumerate(words, start=1):
    if word.startswith(searchWord):
        matches.append(index)
return min(matches) if matches else -1

# Efficient approach (as in the original solution)
for index, word in enumerate(words, start=1):
    if word.startswith(searchWord):
        return index  # Return immediately on first match

5. Off-by-One Indexing Errors Forgetting that the problem requires 1-indexed positions instead of 0-indexed (Python's default) is a common mistake. Using enumerate(words) instead of enumerate(words, start=1) would return incorrect indices.

Solution: Always verify the indexing requirement and use enumerate(words, start=1) for 1-based indexing.