{x}
blog image

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

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.

Solution Explanation: Check If a Word Occurs As a Prefix of Any Word in a Sentence

This problem asks us to find the index (1-indexed) of the first word in a sentence that starts with a given searchWord. If no such word exists, we return -1.

Approach: String Splitting and Prefix Check

The most straightforward approach involves these steps:

  1. Split the sentence: Divide the input sentence into individual words using a space as the delimiter. Most programming languages offer built-in functions for this (e.g., split() in Python, split() in Java, etc.).

  2. Iterate and check: Loop through each word in the resulting list. For each word:

    • Check if the word starts with the searchWord using a prefix check function (e.g., startswith() in Python, startsWith() in Java, etc.).
    • If it's a prefix, immediately return the word's index (plus 1 to make it 1-indexed).

  3. Return -1: If the loop completes without finding a match, return -1 to indicate that no word starts with the given prefix.

Code Examples (with detailed explanations)

Python:

class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        words = sentence.split()  # Split the sentence into a list of words
        for i, word in enumerate(words):  # enumerate gives index and value
            if word.startswith(searchWord):  # Check if the word starts with the searchWord
                return i + 1  # Return the 1-indexed index
        return -1  # Return -1 if no match is found

Java:

class Solution {
    public int isPrefixOfWord(String sentence, String searchWord) {
        String[] words = sentence.split(" "); // Split the sentence into an array of words
        for (int i = 0; i < words.length; i++) {
            if (words[i].startsWith(searchWord)) { // Check for prefix using startsWith()
                return i + 1; // Return 1-indexed index
            }
        }
        return -1; // Return -1 if no match is found
    }
}

C++:

class Solution {
public:
    int isPrefixOfWord(string sentence, string searchWord) {
        stringstream ss(sentence); // Use stringstream for efficient word-by-word reading
        string word;
        int index = 1;
        while (ss >> word) { // Extract words one by one
            if (word.rfind(searchWord, 0) == 0) { // Check if searchWord is a prefix
                return index;
            }
            index++;
        }
        return -1;
    }
};

JavaScript:

/**
 * @param {string} sentence
 * @param {string} searchWord
 * @return {number}
 */
var isPrefixOfWord = function(sentence, searchWord) {
    const words = sentence.split(' '); // Split the sentence
    for (let i = 0; i < words.length; i++) {
        if (words[i].startsWith(searchWord)) { // Use startsWith() for prefix check
            return i + 1; // Return 1-indexed index
        }
    }
    return -1; // Return -1 if no match
};

Time and Space Complexity Analysis

  • Time Complexity: O(m*n) in the worst case, where 'm' is the length of the sentence and 'n' is the length of the searchWord. This is because we might have to iterate through all the words in the sentence and, for each word, perform a prefix check that takes up to O(n) time. However, if a match is found early, the time complexity will be less.

  • Space Complexity: O(m) in the worst case. This is due to the space used to store the list/array of words created by splitting the sentence. In the best case, if the sentence is very short and a match is found quickly, the space complexity would be close to O(1). The space used by searchWord is considered constant because its length is fixed.