algoadvance

Leetcode 1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence

Problem Statement:

Given a sentence that consists of some words separated by a single space, and a searchWord, you need to check if the searchWord is a prefix of any word in the sentence. Return the index of the word (1-indexed) where searchWord is a prefix. If there is no such word, return -1.

Clarifying Questions:

1. What is the range of the length of the sentence and searchWord? The sentence and searchWord lengths can both be reasonably large, say up to 3000 characters.

2. Are there any special characters in the input? The sentence will contain only lowercase English letters and spaces. The searchWord will also contain only lowercase English letters.

3. What if the searchWord is empty? Given the problem constraints, the searchWord will always be a non-empty string.

4. What should be the return value if there is no word in the sentence? Since this scenario is unlikely with the problem constraints (words separated by spaces), you should return -1.

Strategy:

1. Split the Sentence: Split the sentence into an array of words using space as the delimiter.

2. Iterate through the Words: Use a loop to check each word in the array to see if it starts with the searchWord.

3. Return the Index: Since the requirement is to return a 1-indexed position, adjust the index accordingly, and return -1 if no such prefix exists.

Code:

Here is the Java implementation of the solution:

public 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; // converting 0-index to 1-index
            }
        }
        
        return -1; // if no word is found with the given prefix
    }
}

Time Complexity:

• Splitting the Sentence: O(n) where n is the length of the sentence.
• Checking Each Word for the Prefix: Consider m to be the average length of a word. For each word in the sentence, checking if it starts with the searchWord is O(m), and given there are k words, the overall complexity for this check is O(k * m).

The overall time complexity is O(n + k * m), but since k * m is essentially the length of the sentence (n), the final complexity remains O(n).

The space complexity is also O(n) due to the storage of the words array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?