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

EASY

Description

Given a sentence that consists of some words separated by a single space, and a searchWord, check if searchWord is a prefix of any word in sentence.

Return the index of the word in sentence (1-indexed) where searchWord is a prefix of this word. If searchWord is a prefix of more than one word, return the index of the first word (minimum index). If there is no such word return -1.

A prefix of a string s is any leading contiguous substring of s.

Example 1:

Input: sentence = "i love eating burger", searchWord = "burg"
Output: 4
Explanation: "burg" is prefix of "burger" which is the 4th word in the sentence.

Example 2:

Input: sentence = "this problem is an easy problem", searchWord = "pro"
Output: 2
Explanation: "pro" is prefix of "problem" which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.

Example 3:

Input: sentence = "i am tired", searchWord = "you"
Output: -1
Explanation: "you" is not a prefix of any word in the sentence.

Constraints:

1 <= sentence.length <= 100
1 <= searchWord.length <= 10
sentence consists of lowercase English letters and spaces.
searchWord consists of lowercase English letters.

Approaches

Checkout 2 different approaches to solve Check If a Word Occurs As a Prefix of Any Word in a Sentence. Click on different approaches to view the approach and algorithm in detail.

Using String split() and startsWith()

This is the most straightforward approach. We first split the input sentence into an array of individual words using the space character as a delimiter. Then, we iterate through this array of words. For each word, we use the built-in startsWith() method to check if it begins with the searchWord. If a match is found, we return the current word's index (1-based). If we iterate through all the words without finding a prefix match, we return -1.

Algorithm

Use the split(" ") method on the sentence string to get an array of words.
Loop through the words array from index i = 0 to words.length - 1.
Inside the loop, check if words[i].startsWith(searchWord).
If the condition is true, it means we've found the first word that has searchWord as a prefix. Return i + 1 since the problem asks for a 1-indexed result.
If the loop completes without finding any match, return -1.

This method relies on built-in string manipulation functions to simplify the logic. First, the sentence is broken down into a list of words. Then, we check each word in sequence for the required prefix. The first match found is the one we need, so we can return its index immediately.

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; // 1-indexed result
            }
        }
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(N + W*M), where `N` is the length of the `sentence`, `W` is the number of words, and `M` is the length of the `searchWord`. The `split()` operation takes `O(N)` time. The loop runs `W` times, and inside the loop, `startsWith()` takes `O(M)` time in the worst case.Space Complexity: O(N), where `N` is the length of the `sentence`. The `split()` method creates a new array of strings, and the total size of these strings is proportional to the length of the original sentence `N`.

Pros and Cons

Pros:

Simple and easy to understand and implement.
Leverages built-in, highly-optimized library functions.

Cons:

Uses extra space to store the array of words, which can be inefficient for very long sentences.

Code Solutions

Checking out 3 solutions in different languages for Check If a Word Occurs As a Prefix of Any Word in a Sentence. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Check If a Word Occurs As a Prefix of Any Word in a Sentence

Patterns:

Two PointersString Matching

Data Structures:

String

Companies:

Yelp |