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

Problem Statement

The task is to investigate if a given searchWord serves as a prefix for any word found in a provided sentence. Each word in the sentence is separated by a single space. If searchWord functions as a prefix for one or more words, return the 1-indexed position of the first word where it appears. Should the searchWord not act as a prefix for any words, return -1. Understanding a "prefix" is crucial here: it refers to any initial section of a string, which in this context allows us to identify whether the characters of searchWord match from the beginning of any word within sentence.

Examples

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.

Approach and Intuition

The logic needed to solve this problem can be approached by:

1. Split the sentence into individual words using space as a delimiter; this provides a list where each element is a word from the sentence.
2. Iterate through the list of words, and for each word:
   • Check if it starts with the searchWord using a string method like startswith().
   • If true, return the current index of that word, adjusted to be 1-indexed (since list indexes in programming languages like Python start at 0, we add one).
3. If the loop completes without finding a match, return -1 indicating that no words in the sentence have the searchWord as a prefix.

The decision to return the index of the first matching word hinges on the potential for multiple words to share the same prefix. By prioritizing the first occurrence, the solution adheres to seeking the "minimum index." Also, it is noteworthy that by employing string manipulation and direct iteration, the solution remains comprehensible and efficient given the problem constraints.

Solutions

class PrefixNode {
public:
    unordered_map<char, PrefixNode*> map;
    vector<int> positions;
    
    PrefixNode() {}
};
    
class PrefixTree {
public:
    PrefixNode* rootNode;
    
    PrefixTree() { rootNode = new PrefixNode(); }
    
    void insertWord(const string& word, int index) {
        PrefixNode* node = rootNode;
        for (char letter : word) {
            if (node->map.find(letter) == node->map.end()) {
                node->map[letter] = new PrefixNode();
            }
            node = node->map[letter];
            node->positions.push_back(index);
        }
    }
    
    vector<int> searchPrefix(const string& prefix) {
        PrefixNode* node = rootNode;
        for (char letter : prefix) {
            if (node->map.find(letter) == node->map.end()) {
                return {};
            }
            node = node->map[letter];
        }
        return node->positions;
    }
};
    
class Solution {
public:
    int isPrefixOfWord(string sentence, string searchWord) {
        PrefixTree prefixTree;
        istringstream wordsStream(sentence);
        string word;
        int wordIndex = 1;
    
        while (wordsStream >> word) {
            prefixTree.insertWord(word, wordIndex);
            wordIndex++;
        }
    
        vector<int> matchedPositions = prefixTree.searchPrefix(searchWord);
    
        return matchedPositions.empty() ? -1 : *min_element(matchedPositions.begin(), matchedPositions.end());
    }
};