Leetcode – Check If a Word Occurs As a Prefix of Any Word in a Sentence Solution

Spread the love

Among a plethora of problems available on Leetcode, one that particularly hones your string manipulation skills is the “Check If a Word Occurs As a Prefix of Any Word in a Sentence” problem. The problem falls under the string manipulation and searching category.

In this detailed guide, we’ll explore:

  1. Problem Statement
  2. Initial Thoughts & Naive Approach
  3. Optimized Approach
  4. Python Implementations
  5. Test Cases & Edge Cases
  6. Time and Space Complexity Analysis
  7. Conclusion

1. Problem Statement

Given a sentence that consists of some words separated by a single space, and a searchWord, you have to check if searchWord is a prefix of any word in the sentence. Return the index of the word in the 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. Return -1 if there is no such word that searchWord is a prefix of.

Example 1:

Input: sentence = "i love eating burger", searchWord = "burg"
Output: 4
Explanation: “burg” is a prefix of the word “burger” which is present at the 4th position.

Example 2:

Input: sentence = "this problem is an easy problem", searchWord = "pro"
Output: 2
Explanation: “pro” is a prefix of “problem” which is the 2nd word.

2. Initial Thoughts & Naive Approach

One way to approach this problem is to split the sentence into words and then check each word to see if the searchWord is its prefix. The naive approach would involve two nested loops to compare each character.

3. Optimized Approach

Instead of comparing each character of the word and the searchWord, you can use Python’s built-in string methods to achieve the result more elegantly and efficiently.

4. Python Implementations

Naive Implementation

def isPrefixOfWord(sentence, searchWord):
    words = sentence.split(" ")
    for i, word in enumerate(words):
        if word[:len(searchWord)] == searchWord:
            return i + 1  # 1-indexed
    return -1

Optimized Implementation

def isPrefixOfWord(sentence, searchWord):
    for i, word in enumerate(sentence.split(), 1):  # 1-indexed
        if word.startswith(searchWord):
            return i
    return -1

5. Test Cases & Edge Cases

It’s crucial to test the implementation:

# Test 1
assert isPrefixOfWord("i love eating burger", "burg") == 4
# Test 2
assert isPrefixOfWord("this problem is an easy problem", "pro") == 2
# Test 3 (Edge Case)
assert isPrefixOfWord("hello", "hello") == 1
# Test 4 (Edge Case)
assert isPrefixOfWord("hello", "hey") == -1

6. Time and Space Complexity Analysis

Time Complexity

Both the naive and optimized solutions have a time complexity of O(n), where n is the length of the sentence. This is because we have to traverse through each word at least once.

Space Complexity

The space complexity is O(m), where m is the number of words in the sentence. This is due to the storage of these words in a new list.

7. Conclusion

The “Check If a Word Occurs As a Prefix of Any Word in a Sentence” problem is a straightforward string manipulation problem that can be easily solved with Python’s powerful string methods. This problem provides an opportunity to get acquainted with string operations, such as slicing and built-in functions like startswith.

In this guide, we have covered both the naive and optimized Python implementations, several test cases, including edge cases, and analyzed the time and space complexities.

Leave a Reply