You are given a sentence containing words separated by single spaces and a searchWord. Your task is to determine whether searchWord is a prefix of any word in the sentence.

Return the 1-based index of the first word in which searchWord appears as a prefix.

• If searchWord is a prefix of multiple words, return the index of the earliest such word.

• If no word starts with searchWord, return $-1$.

A prefix of a string is any contiguous substring that begins at the first character.

Constraints:

• $1 <=$ sentence.length $<= 100$

• $1 <=$ searchWord.length $<= 10$

• The sentence consists of lowercase English letters and spaces.

• searchWord consists of lowercase English letters.

The key challenge is to efficiently check whether the given searchWord is a prefix of any word in the sentence and return the index of the first match. A simple approach is to scan each word and check if the word starts with searchWord, but this doesn’t leverage the structure of prefixes for efficient matching. The solution begins with splitting the sentence into individual words, allowing us to handle prefix checks more effectively. Instead of scanning each word naively, we use a trie (prefix tree), which stores words character by character and tracks their positions in the sentence. This structure enables fast prefix matching. By inserting words into the trie along with their positions, we ensure that the first successful match corresponds to the smallest index, giving us an efficient way to find the earliest match.

The steps of the algorithm are as follows:

1. Split the sentence into a list of words.

2. Create an object of the Trie.

3. Insert each word from words into the Trie and its position (starting from $1$).

4. After all words have been inserted, check if the searchWord is a prefix of any word in the Trie.

5. If a match is found (i.e., the searchWord exists as a prefix in the Trie), return the smallest index of word where the prefix matches.

6. If no prefix match is found, return $−1$.

Let’s look at the following illustration to get a better understanding of the solution: