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

LeetCode Problem 1455

Difficulty: 🟢 Easy
Topics: Two Pointers, String, String Matching

Solution

Problem Understanding

The problem asks us to determine whether a given searchWord occurs as a prefix of any word within a sentence. A sentence is defined as a string of lowercase English letters separated by single spaces, and a prefix is any contiguous leading substring of a word. We are asked to return the 1-indexed position of the first word in the sentence that starts with searchWord. If no such word exists, we return -1.

The input consists of a sentence and a searchWord, both limited in size (sentence length up to 100, searchWord length up to 10). These constraints indicate that performance is not a major concern since the input is small, but the solution must handle basic string operations correctly.

Important edge cases include: the searchWord being longer than any word in the sentence, searchWord being identical to a full word, searchWord matching multiple words (we need the first), and sentences with only one word.

Approaches

The brute-force approach is straightforward: split the sentence into words, then for each word, check whether searchWord is a prefix. This works because checking a prefix is a simple string operation. Given the constraints, this method is already efficient, but theoretically, it involves iterating over each character of each word until a match is found.

The optimal approach is essentially the same for this problem because the input is small. We use the observation that Python and Go provide efficient string methods (startswith in Python and slicing comparison in Go) that allow checking prefixes in constant time per word, so iterating through the words is sufficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(n)	Split sentence into words and check each prefix; n is number of words, m is length of searchWord
Optimal	O(n * m)	O(n)	Same as brute force but uses built-in prefix check efficiently

Algorithm Walkthrough

1. Split the input sentence by spaces into a list of words.
2. Iterate through the list of words using a 1-indexed counter.
3. For each word, check whether it starts with searchWord.
4. If a match is found, immediately return the current index.
5. If no matches are found after checking all words, return -1.

Why it works: The algorithm maintains the invariant that the first matching word encountered is returned, satisfying the requirement for the minimal index. By checking each word sequentially, no potential prefix match is skipped, ensuring correctness.

Python Solution

class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        words = sentence.split(" ")
        for index, word in enumerate(words, start=1):
            if word.startswith(searchWord):
                return index
        return -1

The Python solution first splits the sentence into words using split(" "). It then enumerates over these words starting from index 1. The startswith method efficiently checks for prefix matches. The first matching word triggers an immediate return, and if no matches are found, -1 is returned.

Go Solution

func isPrefixOfWord(sentence string, searchWord string) int {
    words := strings.Split(sentence, " ")
    for i, word := range words {
        if len(word) >= len(searchWord) && word[:len(searchWord)] == searchWord {
            return i + 1
        }
    }
    return -1
}

In Go, we split the sentence into words using strings.Split. We then iterate over each word, checking if the substring from the start of the word up to the length of searchWord matches searchWord. Indexing is adjusted to be 1-indexed. This handles empty strings safely because the constraints guarantee at least one character in each word.

Worked Examples

Example 1:

Sentence: "i love eating burger", SearchWord: "burg"

Index	Word	Startswith "burg"	Return
1	i	No	-
2	love	No	-
3	eating	No	-
4	burger	Yes	4

Example 2:

Sentence: "this problem is an easy problem", SearchWord: "pro"

Index	Word	Startswith "pro"	Return
1	this	No	-
2	problem	Yes	2
3	is	No	-
4	an	No	-
5	easy	No	-
6	problem	Yes	2

Example 3:

Sentence: "i am tired", SearchWord: "you"

Index	Word	Startswith "you"	Return
1	i	No	-
2	am	No	-
3	tired	No	-
End	-	-	-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * m)	We iterate through n words and for each word compare up to m characters.
Space	O(n)	Splitting the sentence into n words requires additional space.

The time complexity is manageable because the input sentence is short, and the prefix check per word is fast.

Test Cases

# Basic examples
assert Solution().isPrefixOfWord("i love eating burger", "burg") == 4  # matches last word
assert Solution().isPrefixOfWord("this problem is an easy problem", "pro") == 2  # first occurrence
assert Solution().isPrefixOfWord("i am tired", "you") == -1  # no match

# Edge cases
assert Solution().isPrefixOfWord("apple", "a") == 1  # single word, single letter prefix
assert Solution().isPrefixOfWord("apple banana cherry", "ban") == 2  # middle word match
assert Solution().isPrefixOfWord("apple banana cherry", "cherry") == 3  # exact match
assert Solution().isPrefixOfWord("apple banana cherry", "d") == -1  # prefix not present
assert Solution().isPrefixOfWord("aa aa aa", "aa") == 1  # repeated words, return first

Test	Why
"i love eating burger", "burg"	Ensures last word match works
"this problem is an easy problem", "pro"	Checks minimal index is returned when multiple matches exist
"i am tired", "you"	Validates handling of no matches
"apple", "a"	Single word, single character prefix
"apple banana cherry", "ban"	Middle word prefix
"apple banana cherry", "cherry"	Exact word match
"aa aa aa", "aa"	Multiple identical words, should return first occurrence

Edge Cases

1. Single word sentence: If the sentence has only one word, the function must correctly handle 1-indexing and check the prefix. This is managed by enumerating from index 1 and using standard string methods.
2. SearchWord longer than words: If searchWord is longer than any word in the sentence, no matches can occur. The implementation naturally returns -1 because startswith (Python) or slice comparison (Go) fails safely.
3. Multiple matching words: If several words start with the same prefix, the algorithm must return the first. This is ensured because the function returns immediately upon finding the first match, maintaining correctness and minimal index.