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

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

Understanding the Visualization

Input

Sentence with words and search prefix

Process

Check each word for prefix match

Output

Return 1-based index of first match

Key Takeaway

🎯 Key Insight: Split sentence into words and use built-in prefix checking for clean, efficient solution

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

Approach	Time	Space	Notes
✓ Brute Force - Direct String Scanning	O(n × m)	O(1)	Manually scan through the sentence character by character to find words and check prefixes
Split and Built-in Functions	O(n + m)	O(w)	Split sentence into words array and use built-in startsWith function

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Direct String Scanning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler