LC-3045 Hard LeetCode

3045. Count Prefix and Suffix Pairs II

Array String Trie Rolling Hash String Matching Hash Function

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 27% Topics: Array, String, Trie, Rolling Hash, String Matching, Hash Function

Reading material

Arrays & Hashing 12 min Strings 12 min Tries (Prefix Trees) 10 min

Reference solution (spoiler · python)

# Time:  O(n * l)
# Space: O(t)

import collections


# trie
class Solution(object):
    def countPrefixSuffixPairs(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        _trie = lambda: collections.defaultdict(_trie)
        trie = _trie()
        result = 0
        for w in words:
            curr = trie
            for i in xrange(len(w)):
                curr = curr[w[i], w[~i]]
                result += curr["_cnt"] if "_cnt" in curr else 0
            curr["_cnt"] = curr["_cnt"]+1 if "_cnt" in curr else 1
        return result

Solution from kamyu104/LeetCode-Solutions · MIT