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

Easy

Google

1 view

Topics:

Strings

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.

For example:

sentence = "i love eating burger", searchWord = "burg" Output: 4 Explanation: "burg" is a prefix of "burger" which is the 4th word in the sentence.
sentence = "this problem is an easy problem", searchWord = "pro" Output: 2 Explanation: "pro" is a prefix of "problem" which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.
sentence = "i am tired", searchWord = "you" Output: -1 Explanation: "you" is not a prefix of any word in the sentence.

Could you provide a function that takes the sentence and searchWord as input, and returns the index of the first word in the sentence that has the searchWord as a prefix? If no such word exists, return -1.

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

Easy

Google

1 view

Topics:

Strings

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.

For example:

sentence = "i love eating burger", searchWord = "burg" Output: 4 Explanation: "burg" is a prefix of "burger" which is the 4th word in the sentence.
sentence = "this problem is an easy problem", searchWord = "pro" Output: 2 Explanation: "pro" is a prefix of "problem" which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.
sentence = "i am tired", searchWord = "you" Output: -1 Explanation: "you" is not a prefix of any word in the sentence.

Could you provide a function that takes the sentence and searchWord as input, and returns the index of the first word in the sentence that has the searchWord as a prefix? If no such word exists, return -1.

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 or null?
Are the words in the sentence guaranteed to be separated by only one space?
Is the searchWord case-sensitive, or should the prefix match be case-insensitive?
What is the maximum length of the sentence and searchWord strings?
If searchWord is an empty string, what should the return value be?

Brute Force Solution

Approach

The brute force approach involves checking every single word in the sentence to see if the search word appears at the beginning of it. We will check each word individually against the search word to confirm if it is a prefix. If we find a match, we are done; otherwise, we keep checking until we've looked at all the words.

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, compare the beginning of that word with the word we are searching for.
If the search word matches the beginning of the current word, then we have found a match, and we can stop.
If the search word does not match the beginning of the current word, move on to the next word in the sentence and repeat the comparison.
If we reach the end of the sentence without finding any matches, it means the search word is not a prefix of any word in the sentence.

Code Implementation

def is_prefix_of_word_in_sentence(sentence, search_word):
    words_in_sentence = sentence.split()

    for current_word in words_in_sentence:
        # Check if the search word is a prefix of the current word
        if current_word.startswith(search_word):

            # Found a match, no need to continue checking
            return True

        # Move on to the next word if no match

    # If the loop completes without finding a prefix
    return False

Big(O) Analysis

Time Complexity

O(n*m) – The sentence is split into n words, where n is the number of words in the sentence. For each word, a prefix comparison is performed with the search word. In the worst case, the comparison could involve checking all 'm' characters of the search word, where 'm' is the length of the search word. Therefore, the time complexity is proportional to n (number of words) multiplied by m (length of the search word), resulting in O(n*m). In cases where the search word's length 'm' is bounded or significantly smaller than 'n', this can be viewed as O(n).

Space Complexity

O(N) – The space complexity is determined by the auxiliary space used when splitting the sentence into individual words. This split operation typically creates a list of words. In the worst-case scenario, if the sentence contains N words, where N is the number of words in the sentence, this list will hold N word strings. Therefore, the auxiliary space used scales linearly with the number of words in the input sentence, resulting in O(N) space complexity.

Optimal Solution

Approach

We want to quickly see if a given word is the beginning of any word in a sentence. The optimal approach involves splitting the sentence into individual words and then checking only the beginning of each word against the target word.

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

First, break the sentence into individual words.
For each word, see if our target word matches the beginning of it.
If we find a word that starts with our target word, we're done and can say 'yes'.
If we go through all the words and don't find a match, then the target word isn't a prefix of any word in the sentence, so we say 'no'.

Code Implementation

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

    for word in words:
        # Check if search_word is a prefix of the current word.
        if word.startswith(search_word):
            return True

        # If no prefix is found, continue to the next word.

    #If we haven't found prefix in any word
    return False

Big(O) Analysis

Time Complexity

O(n*m) – The sentence is split into n words, where n is the number of words in the sentence. For each of these n words, a prefix comparison is performed with the searchWord. The length of the comparison is bounded by the length of the searchWord, which we'll call m. Therefore, in the worst case, we perform m operations for each of the n words resulting in a total of n*m operations. This gives us a time complexity of O(n*m).

Space Complexity

O(N) – The primary space usage stems from splitting the sentence into individual words. In the worst-case scenario, the sentence could consist of N words (where N is the number of characters in the original sentence, each character being a word separated by a space), resulting in a list of N words being stored in memory. This list represents auxiliary space beyond the original sentence. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
sentence is null or empty	Return -1 immediately, as no prefix can exist in an empty sentence.
searchWord is null or empty	Return 1 if the first word in the sentence exists, otherwise return -1, since an empty string is a prefix of any string.
sentence contains only one word, and searchWord is longer than that word	Return -1, as searchWord cannot be a prefix of a shorter word.
searchWord is longer than the sentence itself	Return -1, as searchWord cannot be a prefix of any word in the sentence.
sentence contains leading or trailing spaces (contrary to the problem statement)	Trim the sentence before processing to conform to the given constraints.
sentence contains multiple consecutive spaces between words (contrary to the problem statement)	Normalize the sentence to have single spaces between words before processing.
sentence contains words with mixed case letters	Convert both sentence words and searchWord to lowercase for case-insensitive comparison.
searchWord is a prefix of multiple words in the sentence.	The solution returns the index of the first matching word, as required by the problem description.