LC-2135 Medium LeetCode

2135. Count Words Obtained After Adding a Letter

Array Hash Table String Bit Manipulation Sorting

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 43% Topics: Array, Hash Table, String, Bit Manipulation, Sorting

Reading material

Arrays & Hashing 12 min Strings 12 min Bit Manipulation 10 min

Reference solution (spoiler · python)

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

class Solution(object):
    def wordCount(self, startWords, targetWords):
        """
        :type startWords: List[str]
        :type targetWords: List[str]
        :rtype: int
        """
        def bitmask(w):
            return reduce(lambda x, y: x|y, (1 << (ord(c)-ord('a')) for i, c in enumerate(w)))

        lookup = set(bitmask(w) for w in startWords)
        result = 0 
        for w in targetWords: 
            mask = bitmask(w)
            result += any(mask ^ (1 << ord(c)-ord('a')) in lookup for c in w)
        return result

Solution from kamyu104/LeetCode-Solutions · MIT