Sponsored
Sponsored
This method involves splitting the input sentence into words and then iterating through each word to check if the searchWord is a prefix of that word. If a match is found, the index of the word (1-based) is returned. If no match is found, -1 is returned.
Time Complexity: O(n * m) where n is the number of words and m is the average length of words.
Space Complexity: O(1).
1#include <iostream>
2#include <sstream>
3#include <string>
4
5using namespace std;
6
7bool isPrefix(string word, string searchWord) {
8 return word.find(searchWord) == 0;
9}
10
11int prefixInSentence(string sentence, string searchWord) {
12 istringstream ss(sentence);
13 string word;
14 int index = 1;
15 while (ss >> word) {
16 if (isPrefix(word, searchWord))
17 return index;
18 index++;
19 }
20 return -1;
21}
22
23int main() {
24 string sentence = "i love eating burger";
25 string searchWord = "burg";
26 cout << prefixInSentence(sentence, searchWord) << endl;
27 return 0;
28}An istringstream is used to read words from the sentence. Each word is checked if the searchWord is a prefix using find. The loop returns the 1-based index of the first occurrence.
This approach uses a two-pointer technique to traverse the sentence and words simultaneously for efficient prefix checking. It doesn't rely on splitting the string into words but rather navigates the sentence using custom logic.
Time Complexity: O(n) where n is the length of the sentence, as it efficiently traverses the string.
Space Complexity: O(1) as only pointers are used.
Utilizes two pointers: i for traversing the sentence and j for the searchWord. Iterates character by character to check prefix while tracking spaces to identify words and reset checks.