Check If a Word is a Prefix of Any Word in a Sentence
Return the 1-indexed position of the first sentence word that starts with `searchWord`, or -1.
3 min read
strings
Problem#
Given a sentence (space-separated words) and a searchWord, return the 1-indexed position of the first word in the sentence that has searchWord as a prefix. Return -1 if no such word exists.
Examples#
sentence = "i love eating burger", searchWord = "burg"→4.sentence = "this problem is an easy problem", searchWord = "pro"→2.sentence = "i am tired", searchWord = "you"→-1.
Constraints#
1 <= sentence.length <= 100,1 <= searchWord.length <= 10.
Hints#
Hint
Tokenize on spaces; check each word with
compare(0, len, searchWord) == 0. Approach#
Split the sentence on spaces. Walk the tokens; the first whose first len(searchWord) characters equal searchWord wins. C++‘s std::string::compare(pos, n, other) does this in O(L).
Solution#
class Solution {public: int isPrefixOfWord(string sentence, string searchWord) { sentence.push_back(' '); int idx = 1, start = 0; for (int i = 0; i < (int)sentence.size(); ++i) { if (sentence[i] == ' ') { int len = i - start; if (len >= (int)searchWord.size() && sentence.compare(start, searchWord.size(), searchWord) == 0) return idx; ++idx; start = i + 1; } } return -1; }};func isPrefixOfWord(sentence string, searchWord string) int { words := strings.Split(sentence, " ") for i, w := range words { if strings.HasPrefix(w, searchWord) { return i + 1 } } return -1}class Solution: def isPrefixOfWord(self, sentence: str, searchWord: str) -> int: for i, w in enumerate(sentence.split(' '), start=1): if w.startswith(searchWord): return i return -1var isPrefixOfWord = function(sentence, searchWord) { const words = sentence.split(' '); for (let i = 0; i < words.length; i++) { if (words[i].startsWith(searchWord)) return i + 1; } return -1;};class Solution { public int isPrefixOfWord(String sentence, String searchWord) { String[] words = sentence.split(" "); for (int i = 0; i < words.length; i++) { if (words[i].startsWith(searchWord)) return i + 1; } return -1; }}function isPrefixOfWord(sentence: string, searchWord: string): number { const words = sentence.split(' '); for (let i = 0; i < words.length; i++) { if (words[i].startsWith(searchWord)) return i + 1; } return -1;}Editorial#
A single pass with token boundaries is enough — no need to materialize a vector of strings or build a trie. The terminator-space trick (sentence.push_back(' ')) makes the final token flush cleanly without a special case.
Complexity#
- Time: O(N).
- Space: O(1).
Concept revision#
Related#