Code Implementation

class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        words = sentence.split()
        for idx, word in enumerate(words):
            if word.startswith(searchWord):
                return idx + 1
        return -1
      

class Solution {
public:
    int isPrefixOfWord(string sentence, string searchWord) {
        istringstream iss(sentence);
        string word;
        int idx = 1;
        while (iss >> word) {
            if (word.find(searchWord) == 0) {
                return idx;
            }
            idx++;
        }
        return -1;
    }
};
      

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;
    }
}
      

var isPrefixOfWord = function(sentence, searchWord) {
    let words = sentence.split(" ");
    for (let i = 0; i < words.length; i++) {
        if (words[i].startsWith(searchWord)) {
            return i + 1;
        }
    }
    return -1;
};
      

Problem Description

Given a string sentence consisting of words separated by single spaces, and a string searchWord, determine if searchWord is a prefix of any word in sentence. Return the index (1-based) of the first word in sentence where searchWord is a prefix. If searchWord is not a prefix of any word, return -1.

• Each word in sentence is separated by a single space.
• Search for the first occurrence where searchWord is a prefix.
• Return the 1-based index of the word (i.e., the first word is index 1).
• If no such word exists, return -1.

Thought Process

To solve this problem, we need to check each word in the given sentence and see if it starts with the searchWord. The most direct way is to split the sentence into its words, then check each word one by one.

A brute-force approach would be to loop through every word and check if the word starts with searchWord. This is acceptable here, as the operations are efficient and the constraints are manageable.

Optimization is not strictly necessary, but we can make sure our solution is clean and leverages built-in string functions for checking prefixes, which are highly optimized.

The key insight is that we only care about the first word where searchWord is a prefix, so we can return immediately when we find it.

Solution Approach

• Step 1: Split the input sentence into a list/array of words using the space character as a delimiter.
• Step 2: Iterate over the list of words, keeping track of the current index (starting from 1, since the answer is 1-based).
• Step 3: For each word, check if it starts with searchWord using a string prefix function (like startswith in Python, startsWith in Java/JavaScript, or find in C++ with index 0).
• Step 4: If a word starts with searchWord, return its index (1-based).
• Step 5: If no word in the sentence is prefixed by searchWord, return -1.

This approach is efficient because it stops as soon as a match is found, and uses built-in string operations for clarity and speed.

Example Walkthrough

Example:
sentence = "i love eating burger"
searchWord = "burg"

1. Split the sentence into words: ["i", "love", "eating", "burger"]
2. Check each word:
   • Word 1: "i" – does not start with "burg"
   • Word 2: "love" – does not start with "burg"
   • Word 3: "eating" – does not start with "burg"
   • Word 4: "burger" – starts with "burg"
3. Since "burger" is the 4th word, and it starts with "burg", we return 4.

If searchWord = "xyz", none of the words start with "xyz", so we return -1.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(N), where N is the number of characters in sentence. Splitting and iterating through the words is linear in the size of the input.
  • Space Complexity: O(W), where W is the number of words, due to storing the split words in an array/list.
• Optimized approach:
  • Time Complexity: O(N), same as above, since we must look at each word at least once in the worst case.
  • Space Complexity: O(W), for the list of words.

Since the problem size is small and the built-in string functions are fast, the straightforward approach is both simple and efficient.

Summary

The solution involves splitting the sentence into words and checking each word to see if it starts with the given searchWord. We return the 1-based index of the first matching word, or -1 if there is no match. This is a classic string manipulation problem that is elegantly solved with built-in functions, and the approach is both readable and efficient.