Same code essentially, but more readable (in Python)

  • 0

    I'd say the key observation is that all words are of the same length. Then it's guaranteed that by adding some offset, you can solve the problem in k passes of the text, given the length of each word is k.

    class Solution:
        # @param S, a string
        # @param L, a list of string
        # @return a list of integer
        def is_match(self, text, tokens, start, word_length, num_tokens):
            if len(text) - start < word_length * num_tokens:
                return False
            partial = collections.defaultdict(int)
            for j in xrange(start, start + num_tokens * word_length, word_length):
                    word = text[j:j+word_length]
                    if word in tokens:
                        partial[word] += 1
                        if partial[word] > tokens[word]:
                            return False
                        return False
            return True
        def findSubstring(self, S, L):
            if not L:
                return []
            num_tokens, word_length = len(L), len(L[0])
            tokens = collections.Counter(L)
            results = []
            for offset in xrange(word_length):
                for i in xrange(offset, len(S), word_length):
                    if self.is_match(S, tokens, i, word_length, num_tokens):
            return results

    By the way, the collections module of Python standard library is automatically imported for you, and it just saves you some codes with defaultdict and Counter.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.