Check If a Word Occurs As a Prefix of Any Word in a Sentence Leetcode Solution


Difficulty Level Easy
Frequently asked in Yelp
String

The problem Check If a Word Occurs As a Prefix of Any Word in a Sentence Leetcode Solution asked us to find the index of the word that starts with a given search word. So, we are given a sentence that has some strings separated by space and another string is a search word. We are told to find if this search word exists as a prefix of any word in the sentence. The word occurs as a prefix means that some word should start with the search word. If there exists more than one word that has the search word as a prefix, return the smallest index. So as usual, before diving deep into the solution let us take a look at a few examples. We are told to follow 1-based indexing when we return the index.

Check If a Word Occurs As a Prefix of Any Word in a Sentence Leetcode Solution

sentence = "i love eating burger", searchWord = "burg"
4

Explanation: The string “burg” exists as a prefix in the word “burger” in the sentence. Since there is only a single word that has the search word as a prefix. We return that index only.

Approach for Check If a Word Occurs As a Prefix of Any Word in a Sentence Leetcode Solution

The problem Check If a Word Occurs As a Prefix of Any Word in a Sentence Leetcode Solution provides us with a sentence. The sentence is some words separated with blank spaces. A sentence does not start and end with blank space. We are also provided a string or word other than this sentence that needs to be searched in the sentence. We are then told to return the smallest index of a word that has the search word as its prefix. So to solve the problem either we split the string as per the spaces. Then just traverse over the words and check if the current word starts with the search word. Performing this operation is simple in Java with split() and startswith() keywords.

The other method to solve the problem is to add a space to the sentence at the start. Afterward, use either the find() function or use the KMP algorithm to find if there exists any word that has our search word as a prefix.

Code to Check If a Word Occurs As a Prefix of Any Word in a Sentence Leetcode Solution

C++ code

#include <bits/stdc++.h>
using namespace std;

int isPrefixOfWord(string sentence, string searchWord) {
    string newSentence = " " + sentence, word = " " + searchWord;
    auto pos = newSentence.find(word);
    if (pos != string::npos)
        return count(begin(newSentence), begin(newSentence) + pos + 1, ' ');
    return -1;
}

int main(){
    string sentence = "i love eating burger";
    string searchWord = "burg";
    cout<<isPrefixOfWord(sentence, searchWord);
}
4

Java code

import java.util.*;
import java.lang.*;
import java.io.*;

class Rough {
    public static int isPrefixOfWord(String sentence, String searchWord) {
        String[] words = sentence.split(" ");
        for (int i = 1; i <= words.length; ++i) {
            if (words[i - 1].startsWith(searchWord)) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) throws IOException {
        String sentence = "i love eating burger";
        String searchWord = "burg";

        System.out.print(isPrefixOfWord(sentence, searchWord));
    }
}
4

Complexity Analysis

Time Complexity

O(N), because we traverse over the whole of the sentence in the worst case. Thus the time complexity is linear.

Space Complexity

O(N), in both of the solutions we create a new array or a new string that takes us space.