DSA Trie

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.

Easy
Time O(N) Space O(1)
LeetCode
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#

Check If a Word is a Prefix of Any Word in a Sentence
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;
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.