1455. 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.

Approach 01:

class Solution {
public:
    int isPrefixOfWord(string sentence, string searchWord) {
        int searchWordLength = searchWord.size();
        cout << searchWordLength << endl;

        vector<string> words;
        stringstream ss(sentence);
        string word;

        while (ss >> word) {
            words.push_back(word);
        }
        for (int wordIndex = 0; wordIndex < words.size(); ++wordIndex) {
            if (words[wordIndex].size() >= searchWordLength) {
                if (words[wordIndex].substr(0, searchWordLength) == searchWord) {
                    cout << words[wordIndex] << endl;
                    return wordIndex + 1;
                }
            }
        }
        return -1;
    }
};

class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        searchWordLength = len(searchWord)
        print(searchWordLength)
        
        words = sentence.split(" ")
        print(words)
        
        for wordIndex, word in enumerate(words):
            if len(word) >= searchWordLength:
                if word[:searchWordLength] == searchWord:                    
                    print(word)
                    return wordIndex + 1
        return -1

Time Complexity

• Splitting the sentence into words:

  The sentence is split into words using a stringstream, which involves iterating over all characters in the string. Let \(N\) be the length of the sentence. This step takes \(O(N)\).

• Checking each word:

  Each word is compared with the search word using the substr method. Let \(W\) be the number of words in the sentence and \(L\) be the length of the search word. In the worst case, each word has a length close to \(N/W\), leading to \(O(W \cdot L)\) comparisons.

• Overall Time Complexity:

  Combining these steps, the overall time complexity is \(O(N + W \cdot L)\). Since \(W \cdot L \leq N\), this simplifies to \(O(N)\).

Space Complexity

• Words vector:

  The vector stores all words in the sentence. In the worst case (all characters are non-space), the number of words is 1, and the space complexity is \(O(N)\) to store the entire sentence as one word.

• Stringstream and intermediate strings:

  The stringstream and intermediate strings for splitting and checking substrings use additional memory, but this is proportional to the input size. This contributes \(O(N)\).

• Overall Space Complexity:

  The overall space complexity is \(O(N)\), primarily due to the storage of words in the vector.