# Check If a Word Occurs As a Prefix of Any Word in a Sentence
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-a-word-occurs-as-a-prefix-of-any-word-in-a-sentence)
Canonical: https://scaleengineer.com/dsa/problems/check-if-a-word-occurs-as-a-prefix-of-any-word-in-a-sentence
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [String Matching](https://scaleengineer.com/dsa/patterns/string-matching)
**Data structures:** String
**Companies:** [Yelp](https://scaleengineer.com/companies/yelp)
---
## Problem
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
## 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.
**Time:** 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:** 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:** 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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Single Pass without Extra Space
This approach improves upon the first one by avoiding the creation of an intermediate array of words, thus reducing the space complexity to be constant. We can iterate through the sentence character by character, keeping track of the current word index. When we detect the beginning of a new word (either at the start of the sentence or after a space), we check if that word starts with the `searchWord`.
**Time:** O(N * M), where `N` is the length of the `sentence` and `M` is the length of `searchWord`. We iterate through the sentence once (`O(N)`). At the beginning of each word, we perform a `startsWith` check which can take up to `O(M)` time. This gives a worst-case complexity of `O(N*M)`. · **Space:** O(1). This approach uses only a few variables to keep track of the state (`i`, `wordIndex`), and does not create any data structures whose size depends on the input length.
**Pros:** Highly space-efficient (`O(1)` space).; Processes the sentence in a single pass without creating intermediate data structures.
**Cons:** The logic can be slightly more complex to write and reason about compared to the `split()` approach.
### Explanation
By manually parsing the string, we can avoid the overhead of creating a new array of strings. We iterate through the sentence, and every time we encounter the beginning of a word, we perform the prefix check. The beginning of a word is identified as either the very first character of the sentence or a character that immediately follows a space. We also keep a counter for the word index, which is incremented every time we pass a space.

```java
class Solution {
    public int isPrefixOfWord(String sentence, String searchWord) {
        int n = sentence.length();
        int wordIndex = 1;
        for (int i = 0; i < n; ++i) {
            // Check if it's the start of a word
            if (i == 0 || sentence.charAt(i - 1) == ' ') {
                // Use the built-in startsWith with an offset
                if (sentence.startsWith(searchWord, i)) {
                    return wordIndex;
                }
            }
            // Increment word index when a space is encountered
            if (sentence.charAt(i) == ' ') {
                wordIndex++;
            }
        }
        return -1;
    }
}
```
### Algorithm
- Initialize a `wordIndex` counter to 1.
- Iterate through the `sentence` string with an index `i` from 0 to the end.
- At each character, check if it marks the beginning of a word. A character at index `i` is the start of a word if `i` is 0, or if the character at `i-1` is a space.
- If it is the start of a word, use a function like `sentence.startsWith(searchWord, i)` to check for a prefix match starting from the current position `i`.
- If a match is found, return the current `wordIndex`.
- If the character at index `i` is a space, it signifies the end of the current word, so we increment `wordIndex`.
- If the loop finishes without returning, it means no match was found. Return -1.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  int isPrefixOfWord(string sentence, string searchWord) {
    stringstream ss(sentence);
    string s;
    for (int i = 1; ss >> s; ++i) {
      if (s.find(searchWord) == 0) {
        return i;
      }
    }
    return -1;
  }
};

```

### Python

```python
class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int: for i, s in enumerate(sentence . split(), 1): if s . startswith(searchWord): return i return - 1

```