algoadvance

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

Problem Statement

You are given a sentence and a search word. The objective is to check if the search word occurs as a prefix of any word in the given sentence. If the search word is a prefix of a word in the sentence, return the index (1-based) of the first such word. If the search word does not occur as a prefix of any word in the sentence, return -1.

Example:

Clarifying Questions

  1. Are the words in the sentence separated by single spaces?
  2. Can the input sentence contain punctuation marks or special characters?
  3. Is there any limitation on the length of the input sentence or the search word?

Strategy

  1. Split the given sentence by spaces to extract individual words.
  2. Iterate through the list of words and check if the search word is a prefix of any word using the substr or find function.
  3. Return the (1-based) index of the first word for which the search word is a prefix.
  4. If no such prefix is found, return -1.

Code

#include <iostream>
#include <sstream>
#include <string>

int isPrefixOfWord(std::string sentence, std::string searchWord) {
    std::istringstream stream(sentence);
    std::string word;
    int index = 1;
    
    while (stream >> word) {
        if (word.find(searchWord) == 0) {
            return index;
        }
        index++;
    }
    
    return -1;
}

int main() {
    // Test cases
    std::cout << isPrefixOfWord("i love eating burger", "burg") << std::endl; // Output: 4
    std::cout << isPrefixOfWord("this problem is an easy problem", "pro") << std::endl; // Output: 2
    std::cout << isPrefixOfWord("i am tired", "you") << std::endl; // Output: -1

    return 0;
}

Time Complexity

In the worst case, the time complexity will be O(n * k) where n is the number of words and k is the length of the search word.

Thus, the overall time complexity is O(n * k). This is efficient given the context of typical sentence and word lengths.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI