Statement▼
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
searchWordis 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
sentenceconsists of lowercase English letters and spaces.searchWordconsists of lowercase English letters.
Solution
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:
Split the
sentenceinto a list ofwords.Create an object of the
Trie.Insert each word from
wordsinto theTrieand its position (starting from1 ).After all
wordshave been inserted, check if thesearchWordis a prefix of anywordin theTrie.If a match is found (i.e., the
searchWordexists as a prefix in the Trie), return the smallest index ofwordwhere the prefix matches.If no prefix match is found, return
−1 .
Let’s look at the following illustration to get a better understanding of the solution: