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 insentence _(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.

Examples

Example 1:

1
2
3

Input: sentence = "i love eating burger", searchWord = "burg"
Output: 4
Explanation: "burg" is prefix of "burger" which is the 4th word in the sentence.

Example 2:

1
2
3

Input: sentence = "this problem is an easy problem", searchWord = "pro"
Output: 2
Explanation: "pro" is prefix of "problem" which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.

Example 3:

1
2
3

Input: sentence = "i am tired", searchWord = "you"
Output: -1
Explanation: "you" is not a prefix of any word in the sentence.

Constraints:

  • 1 <= sentence.length <= 100
  • 1 <= searchWord.length <= 10
  • sentence consists of lowercase English letters and spaces.
  • searchWord consists of lowercase English letters.

Solution

Method 1 - Using split

One of the easiest way can be that we can split the string around space, and check if any word starts with the searchWord. Here is the approach:

  1. Split the input sentence into words using space as the delimiter.
  2. Iterate through the list of words and check if searchWord is a prefix of the current word.
  3. Return the index of the first word (1-indexed) where searchWord is a prefix.
  4. If no such word is found, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7

class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        words: List[str] = sentence.split(' ')
        for i, word in enumerate(words):
            if word.startswith(searchWord):
                return i + 1
        return -1

Complexity

  • ⏰ Time complexity: O(n*m) where n is the number of words in the sentence and m is the average length of a word. The startswith function operates in O(m).
  • 🧺 Space complexity: O(n) for storing words after splitting the sentence.

Method 2 - Without using split function but indexOf and two pass

To simplify the implementation, we prepend a space to both the sentence and the searchWord. This allows us to perform a string search and count the number of spaces preceding the found word.

Here is the approach:

  1. By adding a leading space, we ensure that searchWord is treated as a whole word and not as a substring within a word.
  2. Perform a string search to locate the position where searchWord appears in the sentence.
  3. Count the number of spaces from the beginning of the modified sentence to the position of the found word to calculate its 1-indexed position.
  4. If searchWord is not found, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int isPrefixOfWord(String sentence, String searchWord) {
        String modifiedSentence = " " + sentence;
        String word = " " + searchWord;
        int pos = modifiedSentence.indexOf(word);

        if (pos != -1) {
            int spaceCount = 0;
            for (int i = 0; i <= pos; i++) {
                if (modifiedSentence.charAt(i) == ' ') {
                    spaceCount++;
                }
            }
            return spaceCount;
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        modified_sentence = " " + sentence
        word = " " + searchWord
        pos = modified_sentence.find(searchWord)
        
        if pos != -1:
            space_count = modified_sentence[:pos + 1].count(' ')
            return space_count
        return -1

Complexity

  • ⏰ Time complexity: O(n * m) where n is the length of the sentence and m is the length of the searchWord. The indexOf/find operation is O(n*m) and counting spaces is O(n).
  • 🧺 Space complexity: O(n + m) due to the concatenation of the sentence and searchWord with spaces.

Method 3 - Using 2 Pointer technique and add spaces to string and word

Here is approach using 2 pointers:

  1. Append a space at the beginning of both the sentence and searchWord to ensure they are treated as whole words.
  2. Use two pointers: one (i) to traverse the sentence and another (j) to traverse the searchWord.
  3. Count the number of spaces (wordCount) encountered as we traverse the sentence.
  4. If characters match, increment the pointer (j) of the searchWord. If characters do not match, reset (j) based on the first character of the searchWord.
  5. If j reaches the length of the searchWord, return the count of words.
  6. If the end of the sentence is reached without a match, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int isPrefixOfWord(String sentence, String searchWord) {
        String modifiedSentence = " " + sentence;
        String word = " " + searchWord;
        int wordCount = 0, j = 0;

        for (int i = 0; i < modifiedSentence.length() && j < word.length(); i++) {
            if (modifiedSentence.charAt(i) == ' ') {
                wordCount++;
            }
            if (modifiedSentence.charAt(i) == word.charAt(j)) {
                j++;
            } else {
                j = modifiedSentence.charAt(i) == word.charAt(0) ? 1 : 0;
            }
        }
        return j == word.length() ? wordCount : -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        modified_sentence = " " + sentence
        word = " " + searchWord
        word_count, j = 0, 0

        for i in range(len(modified_sentence)):
            if j >= len(word):
                break
            if modified_sentence[i] == ' ':
                word_count += 1
            if modified_sentence[i] == word[j]:
                j += 1
            else:
                j = 1 if modified_sentence[i] == word[0] else 0

        return word_count if j == len(word) else -1

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the sentence and m is the length of the searchWord.
  • 🧺 Space complexity: O(n + m) due to the concatenation of the sentence and searchWord with spaces.

Method 4 - two pointer technique without using extra space

Here is the approach:

  1. Initialization:
    • wordCount starts at 1 to account for the first word.
    • j is used to track the position in searchWord.
  2. Iteration:
    • Traverse the sentence character by character.
    • Each time a space is encountered, increment wordCount since it’s the start of a new word.
  3. Character Matching:
    • If the current character in the sentence matches the current character in the searchWord:
      • Increment j if it’s already more than 0.
      • For the first character (j == 0), increment j only if it’s the start of the sentence or after a space.
    • If j equals the length of the searchWord, return the current wordCount.
  4. Mismatch Handling:
    • If the characters do not match, reset j to 0 to start matching searchWord afresh from the next position in the sentence.
  5. Termination:
    • If the loop ends without completing a match for the searchWord, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int isPrefixOfWord(String sentence, String searchWord) {
        int wordCount = 1, j = 0;

        for (int i = 0; i < sentence.length() && j < searchWord.length(); i++) {
            if (sentence.charAt(i) == ' ') {
                wordCount++;
            }
            if (sentence.charAt(i) == searchWord.charAt(j)) {
                j = j > 0 ? j + 1 : (i == 0 || sentence.charAt(i - 1) == ' ') ? 1 : 0;
            } else {
                j = 0;
            }
        }

        return j == searchWord.length() ? wordCount : -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        word_count, j = 1, 0
        
        for i in range(len(sentence)):
            if j >= len(searchWord):
                break
            
            if sentence[i] == ' ':
                word_count += 1
            
            if sentence[i] == searchWord[j]:
                if j > 0:
                    j += 1
                else:
                    if i == 0 or sentence[i - 1] == ' ':
                        j = 1
                    else:
                        j = 0
            else:
                j = 0
        
        return word_count if j == len(searchWord) else -1

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)