LeetCode Entry

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

02.12.2024 easy 2024 kotlin rust

Position of the prefix

1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence easy blog post substack youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/819

Problem TLDR

Position of the prefix #easy

Intuition

The O(n) time and O(1) memory solution is possible (see c++).

Approach

• we can prepend a word to shorten the index adjusting logic
• c++ will shoot in your foot for comparing -1 with .size()
• rust has a nice .map_or

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\) or O(1)

Code

    fun isPrefixOfWord(sentence: String, searchWord: String) =
        .indexOfFirst { it.startsWith(searchWord) }

    pub fn is_prefix_of_word(sentence: String, search_word: String) -> i32 {
        sentence.split_whitespace().position(|w| w.starts_with(&search_word))
        .map_or(-1, |i| 1 + i as i32)
    }

    int isPrefixOfWord(string s, string w) {
        int p = 1, j = 0, n = w.size();
        for (int i = 0; i < s.size() && j < n; ++i)
            s[i] == ' ' ? j = 0, ++p :
            j >= 0 && s[i] == w[j] ? ++j : j = -1;
        return j < n ? -1 : p;
    }