algoadvance

Given a sentence consisting of a string of words separated by spaces, and a search word, determine if the search word appears as a prefix of any word in the sentence. If it does, return the index (1-indexed) of the first word in the sentence that has the search word as a prefix. If the search word is not a prefix of any word in the sentence, return -1.

Example:

1. Input: sentence = "i love eating burger", searchWord = "burg"
   • Output: 4
2. Input: sentence = "this problem is an easy problem", searchWord = "pro"
   • Output: 2
3. Input: sentence = "i am tired", searchWord = "you"
   • Output: -1

Clarifying Questions

1. Can the sentence contain punctuation marks?
   • No, the sentence consists of words separated by spaces only.
2. Are we guaranteed that the input sentence is not empty?
   • Yes.
3. Is the search word guaranteed to be non-empty?
   • Yes.

Strategy

1. Split the sentence into words.
2. Iterate through the list of words with their indices.
3. Check if the search word is a prefix of the current word.
4. If it is, return the current index (1-indexed).
5. If no words in the sentence have the search word as a prefix, return -1.

Code

def isPrefixOfWord(sentence: str, searchWord: str) -> int:
    words = sentence.split()
    for index, word in enumerate(words):
        if word.startswith(searchWord):
            return index + 1  # returning 1-indexed position
    return -1

# Example Test Cases
print(isPrefixOfWord("i love eating burger", "burg"))  # Output: 4
print(isPrefixOfWord("this problem is an easy problem", "pro"))  # Output: 2
print(isPrefixOfWord("i am tired", "you"))  # Output: -1

Time Complexity

• Splitting the sentence into words will take O(n) time, where n is the length of the sentence.
• Iterating through the list of words also takes O(m) time, where m is the number of words.
• Checking if a word starts with the search word takes O(p) time in the worst case for each word, where p is the length of the search word.

Overall time complexity is O(n + k*p), where:

• n is the length of the sentence,
• k is the number of words in the sentence,
• p is the length of the search word.

This solution should be efficient for most practical inputs.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?