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

Easy

Yelp

2 views

Topics:

ArraysStrings

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.

Try coding it in LeetCode

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

Easy

Yelp

2 views

Topics:

ArraysStrings

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the sentence or searchWord be empty strings?
Is searchWord guaranteed to contain only lowercase English letters, like the words in sentence?
What is the maximum length of the sentence and searchWord?
If searchWord is an empty string, should I consider it a prefix of every word and return the index of the first word?
Are the words in the sentence guaranteed to be separated by exactly one space?

Brute Force Solution

Approach

We're given a sentence and a search word. The brute force method involves checking if the search word is the beginning part of any word in the sentence. We'll look at each word in the sentence one by one and compare it with the search word.

Here's how the algorithm would work step-by-step:

Take the sentence and split it into individual words.
For each word in the sentence, check if the search word matches the beginning part of that word.
If the search word matches the start of a word in the sentence, then we've found a match and we're done.
If we've checked all the words in the sentence and found no match, then the search word isn't a prefix of any word in the sentence.

Code Implementation

def is_prefix_of_word(sentence, search_word):
    words = sentence.split()

    # Iterate through each word in the sentence
    for word_index in range(len(words)):
        current_word = words[word_index]

        # Check if the search word is a prefix of the current word.
        # This ensures we're only looking at the beginning.
        if current_word.startswith(search_word):
            return word_index + 1

    #If the search word is not a prefix of any word.
    return -1

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through each word in the sentence, where 'n' is the number of words in the sentence. For each word, it compares the search word with a prefix of that word. In the worst case, the comparison involves checking all characters of the search word, which we can denote as length 'm'. Therefore, the time complexity is proportional to the number of words in the sentence multiplied by the length of the search word. Thus the time complexity is O(n*m).

Space Complexity

O(N) – The space complexity is primarily determined by splitting the input sentence into individual words. This operation creates a list of words, and in the worst-case scenario, where the sentence consists of N words, where N is the number of words in the sentence, the list will hold N strings. Therefore, the auxiliary space required scales linearly with the number of words in the sentence. This leads to a space complexity of O(N).

Optimal Solution

Approach

The problem asks if a given word appears at the beginning of any word in a sentence. We can solve this efficiently by checking each word in the sentence one by one and stopping as soon as we find a match. This avoids unnecessary comparisons.

Here's how the algorithm would work step-by-step:

First, split the sentence into individual words.
Then, go through each word in the sentence, one at a time.
For each word, check if the given word starts it.
If the given word is at the beginning of the current word, then we've found a match, and we can stop looking.
If we go through all the words and don't find a match, then the given word is not a prefix of any word in the sentence.

Code Implementation

def is_prefix_of_word(sentence, search_word):
    words = sentence.split()

    # Iterate through each word in the sentence
    for word in words:
        # Check if the search word is a prefix
        if word.startswith(search_word):
            return True

    # If no word starts with search_word
    return False

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the number of words in the sentence and m be the length of the prefix word. The algorithm iterates through each word in the sentence, which takes O(n) time. For each word, it checks if the prefix word is a prefix of that word, which takes O(m) time in the worst case (where we compare all characters of the prefix with the beginning of the current word in the sentence). Therefore, the overall time complexity is O(n*m) because we iterate through n words and perform an O(m) operation on each.

Space Complexity

O(N) – The primary space complexity comes from splitting the sentence into individual words. This creates a list of words, whose size, in the worst case, is proportional to the number of words in the sentence. Therefore, the auxiliary space required to store the split words is directly dependent on the sentence length, represented as N where N is the number of words in the sentence. Thus the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty sentence string	Return -1 immediately since no words exist.
Null sentence or searchWord	Throw an IllegalArgumentException or return -1, depending on requirements.
Empty searchWord	Return 1 if sentence is not empty, otherwise return -1 because every word technically starts with an empty string.
Search word longer than the sentence itself	Return -1 immediately since the search word cannot be a prefix of any word in the sentence.
Sentence with leading or trailing spaces (against instructions)	Trim the sentence string before processing to remove leading/trailing spaces.
Sentence with multiple spaces between words	Split the sentence using one or more spaces as delimiters.
Search word is a prefix of the entire sentence	The solution should correctly identify the first word if it starts with the search word, even if the sentence is only one word long and it starts with the search word.
Very long sentence and searchWord to test scalability	Ensure the solution uses efficient string processing to avoid excessive time complexity for large inputs.