LC-1455 Easy LeetCode

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

Read the full problem statement on LeetCode.

Difficulty: easy Acceptance: 69% Topics: Two Pointers, String, String Matching

Reading material

Two Pointers 9 min Strings 12 min String Matching & Hashing 13 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class Solution(object):
    def isPrefixOfWord(self, sentence, searchWord):
        """
        :type sentence: str
        :type searchWord: str
        :rtype: int
        """
        def KMP(text, pattern):
            def getPrefix(pattern):
                prefix = [-1] * len(pattern)
                j = -1
                for i in xrange(1, len(pattern)):
                    while j > -1 and pattern[j + 1] != pattern[i]:
                        j = prefix[j]
                    if pattern[j + 1] == pattern[i]:
                        j += 1
                    prefix[i] = j
                return prefix
    
            prefix = getPrefix(pattern)
            j = -1
            for i in xrange(len(text)):
                while j != -1 and pattern[j+1] != text[i]:
                    j = prefix[j]
                if pattern[j+1] == text[i]:
                    j += 1
                if j+1 == len(pattern):
                    return i-j
            return -1
        
        if sentence.startswith(searchWord):
            return 1
        p = KMP(sentence, ' ' + searchWord)
        if p == -1:
            return -1
        return 1+sum(sentence[i] == ' ' for i in xrange(p+1))

Solution from kamyu104/LeetCode-Solutions · MIT