• Leetcode POTDs

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

Problem Statement

Link - Problem 1455

Question

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.

Solution

class Solution {
public:
    int isPrefixOfWord(string sentence, string searchWord) {
        vector<string> words;
        string temp = "";

        for (char ch : sentence) {
            if (ch == ' ') {
                if (!temp.empty()) {
                    words.push_back(temp);
                    temp = "";
                }
            } else {
                temp += ch;
            }
        }
        if (!temp.empty()) {
            words.push_back(temp);
        }

        for (int i = 0; i < words.size(); i++) {
            if (words[i].substr(0, searchWord.size()) == searchWord) {
                return i + 1;
            }
        }

        return -1;
    }
};

Complexity Analysis

| Algorithm           | Time Complexity | Space Complexity |
| ------------------- | --------------- | ---------------- |
| String Tokenization | O(nm)      | O(n)             |

Explanation

Intial Thoughts

To solve this problem, we need to think of a way to break down the sentence into individual words. One approach could be to use the space as a delimiter to split the sentence into words. Another crucial thing to consider is how we will be comparing the searchWord with each word in the sentence. A prefix comparison will be necessary, and we need to think of a way to achieve that. Lastly, we need to consider the edge case where the searchWord is not a prefix of any word in the sentence.

Intuitive Analysis

Intuitively, we can solve this problem by breaking it down into three main steps. Firstly, we need to create a list of all words in the sentence, which can be achieved by splitting the sentence at each space. Secondly, we need to iterate over each word in the list and check if the searchWord is a prefix of that word. If it is, we need to return the index of that word. Lastly, we need to ensure that we return the index of the first word that the searchWord is a prefix of, which can be achieved by returning the index as soon as we find a match.

1. Intuition

• The problem requires finding the index of the first word in a sentence that has a given search word as its prefix.
• To solve this problem, we need to split the sentence into individual words and then check each word to see if it starts with the search word.
• We can use the substr function in C++ to check if a word starts with the search word.
• The key insight here is that we only need to return the index of the first word that matches the search word, so we can stop checking as soon as we find a match.
• This solution works because it checks each word in the sentence in order, so it will always find the first word that matches the search word.
• The time complexity of this solution is O(nm), where n is the number of words in the sentence, because we need to check each word once and logm is the time complexity of the substr function.
• The space complexity is also O(n), because we need to store all the words in the sentence in a vector.

2. Implementation

• We start by splitting the sentence into individual words using a for loop and a temporary string temp to build each word.
• We use the line if (ch == ' ') to check if we have reached the end of a word, and if so, we add the word to the words vector.
• After splitting the sentence into words, we use another for loop to check each word to see if it starts with the search word.
• We use the line if (words[i].substr(0, searchWord.size()) == searchWord) to check if a word starts with the search word.
• If we find a word that starts with the search word, we return the index of that word plus one, because the problem uses 1-based indexing.
• If we don’t find any words that start with the search word, we return -1 to indicate that no match was found.
• We use the line if (!temp.empty()) to check if the temporary string is not empty before adding it to the words vector, to avoid adding an empty string to the vector.

Complexity Analysis

Time Complexity:

• The algorithm iterates over the input sentence once to split it into words, resulting in O(n) time complexity where n is the length of the sentence.
• For each word, it performs a substring check to compare the word with the search word, contributing an additional O(m) factor to the time complexity where m is the length of the search word.
• Since the loop iterates over the words array (of size n) and checks substrings of size m, the overall time complexity is O(n*m) due to the substring checks.
• However, given that string comparison typically involves a constant-time comparison for each character (worst-case when the words are identical), we need to account for the average and worst case. Thus, the overall time complexity can be classified as O(n*m).

Space Complexity:

• The algorithm creates an additional data structure, a vector to hold the word tokens, requiring memory proportionate to the number of words in the sentence.
• This requires auxiliary space that scales with the input size. Assuming an average case where each word is roughly equally long, this contributes to a space complexity of O(n) where n is the number of words (which can be related to the length of the sentence) rather than its characters.
• The string variables ’temp’ and ‘searchWord’ and local variables require constant space, thus not impacting the overall space complexity. Consequently, the space complexity of the algorithm can be classified as O(n).

Footnote

This question is rated as Easy difficulty.

Hints

First extract the words of the sentence.

Check for each word if searchWord occurs at index 0, if so return the index of this word (1-indexed)

If searchWord doesn’t exist as a prefix of any word return the default value (-1).

Similar Questions: