Check If a Word Occurs As a Prefix of Any Word in a Sentence - 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.

Input & Output

Example 1 — Basic Prefix Match

$ Input: sentence = "i love eating burger", searchWord = "burg"

› Output: 4

💡 Note: "burg" is a prefix of "burger" which is the 4th word in the sentence

Example 2 — First Match

$ Input: sentence = "this problem is an easy problem", searchWord = "pro"

› Output: 2

💡 Note: "pro" is a prefix of "problem" which appears at positions 2 and 6, return the first occurrence at index 2

Example 3 — No Match

$ Input: sentence = "i am tired", searchWord = "you"

› Output: -1

💡 Note: "you" is not a prefix of any word in "i am tired"

Constraints

1 ≤ sentence.length ≤ 100
1 ≤ searchWord.length ≤ 10
sentence consists of lowercase letters and spaces
sentence does not have leading or trailing spaces
All the words in sentence are separated by a single space

Visualization

Tap to expand

Asked in

a Amazon 3 f Facebook 2

The key insight is to split the sentence into words and use built-in prefix checking functions. Best approach is split and startsWith for clean, reliable code. Time: O(n+m), Space: O(w).

Common Approaches

✓ Brute Force - Direct String Scanning

⏱️ Time: O(n × m) Space: O(1)

Iterate through each character in the sentence, manually identify word boundaries, and for each word check if it starts with the searchWord by comparing characters one by one.

Split and Built-in Functions

⏱️ Time: O(n + m) Space: O(w)

Use string split method to convert sentence into an array of words, then iterate through the array using built-in prefix checking functions for cleaner and more reliable code.

Brute Force - Direct String Scanning — Algorithm Steps

Step 1: Scan sentence character by character to identify words
Step 2: For each word found, manually compare with searchWord character by character
Step 3: Return 1-based index of first matching word, or -1 if none found

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Characters

Move through sentence identifying word boundaries

Manual Comparison

Compare each word character by character with searchWord

Return Index

Return 1-based index of first matching word

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int solution(char* sentence, char* searchWord) {
    int wordIndex = 1;
    int wordStart = 0;
    int i = 0;
    int sentenceLen = strlen(sentence);
    int searchLen = strlen(searchWord);
    
    while (i <= sentenceLen) {
        // End of sentence or found space (end of current word)
        if (i == sentenceLen || sentence[i] == ' ') {
            if (i > wordStart) {  // We have a word
                int wordLen = i - wordStart;
                // Check if searchWord is prefix of current word
                if (wordLen >= searchLen) {
                    bool match = true;
                    for (int j = 0; j < searchLen; j++) {
                        if (sentence[wordStart + j] != searchWord[j]) {
                            match = false;
                            break;
                        }
                    }
                    if (match) {
                        return wordIndex;
                    }
                }
                wordIndex++;
            }
            wordStart = i + 1;
        }
        i++;
    }
    
    return -1;
}

int main() {
    char sentence[1000];
    char searchWord[1000];
    
    fgets(sentence, sizeof(sentence), stdin);
    sentence[strcspn(sentence, "\n")] = 0;
    
    fgets(searchWord, sizeof(searchWord), stdin);
    searchWord[strcspn(searchWord, "\n")] = 0;
    
    int result = solution(sentence, searchWord);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

n is sentence length, m is searchWord length - we potentially check every character in sentence against searchWord

✓ Linear Growth

Space Complexity

O(1)

Only using variables for tracking position and comparison

✓ Linear Space

12.0K Views

Medium Frequency

~10 min Avg. Time

445 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Direct String Scanning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler