HashTable Summary

Summary of HashTable.

LeetCode 242 Valid Anagram

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        HashTable = [0] * 26
        for i in range(len(s)):
            HashTable[ord(s[i]) - ord('a')] += 1
        for j in range(len(t)):
            HashTable[ord(t[j]) - ord('a')] -= 1
        for q in range(26):
            if HashTable[q] != 0:
                return False

        return True

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s_dict = collections.defaultdict(int)
        t_dict = collections.defaultdict(int)

        for i in s:
            s_dict[i] += 1
        for j in t:
            t_dict[j] += 1

        return s_dict == t_dict

Similar: LeetCode 383 Ransom Note, LeetCode 49 Group Anagrams, LeetCode 438 Find All Anagrams in a String.

LeetCode 349 Intersection of Two Arrays

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        table1 = collections.defaultdict(int)
        table2 = collections.defaultdict(int)
        for i in range(len(nums1)):
            table1[nums1[i]] += 1
        for i in range(len(nums2)):
            table2[nums2[i]] += 1
        res=[]
        for i in table1.keys():
            if i in table2.keys():
                res.append(i)
        return res

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        table1 = collections.Counter(nums1)
        table2 = collections.Counter(nums2)
        res=[]
        for i in table1.keys():
            if i in table2.keys():
                res.append(i)
        return res

Similar: LeetCode 350 Intersection of Two Arrays II

LeetCode 202 Happy Number

class Solution:
    def isHappy(self, n: int) -> bool:
        def calculation(n):
            SUM = 0
            while n > 0:
                SUM += (n % 10) ** 2
                n = n // 10
            return SUM

        SET = set()
        while n != 1 and n not in SET:
            SET.add(n)
            n = calculation(n)
        
        return n == 1

LeetCode 1 Two Sum

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        tab = dict()
        for idx, num in enumerate(nums):
            if target-num not in tab:
                tab[num] = idx
            else:
                return [tab[target-num], idx]

LeetCode 454 4 Sum II

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        tab = dict()
        for n1 in nums1:
            for n2 in nums2:
                if n1+n2 in tab:
                    tab[n1+n2] += 1
                else:
                    tab[n1+n2] = 1

        count = 0
        for n3 in nums3:
            for n4 in nums4:
                key = -n3-n4
                if key in tab:
                    count += tab[key] # there can be duplicates
        return count

LeetCode 383 Ransom Note

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        HashTable = [0] * 26
        for i in range(len(magazine)):
            HashTable[ord(magazine[i]) - ord('a')] += 1
        for j in range(len(ransomNote)):
            HashTable[ord(ransomNote[j]) - ord('a')] -= 1
        print(HashTable)
        for q in range(len(HashTable)):
            if HashTable[q] < 0:
                return False

        return True

LeetCode 15 3 Sum

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)
        nums.sort()
        for i in range(n):
            left = i+1
            right = n-1
            if nums[i] > 0:
                break # impossible to sum to 0
            if i > 0 and nums[i] == nums[i-1]:
                continue # remove duplicates

            while left < right:
                SUM = nums[i] + nums[left] + nums[right]
                if SUM > 0:
                    right -= 1
                elif SUM < 0:
                    left += 1
                else:
                    res.append([nums[i], nums[left], nums[right]])
                    while left != right and nums[right-1] == nums[right]:
                        right -= 1 # remove duplicates
                    while left != right and nums[left+1] == nums[left]:
                        left += 1 # remove duplicates
                    left += 1
                    right -= 1
        return res

LeetCode 18 4 Sum

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        res = []
        n = len(nums)
        nums.sort()

        for i in range(n):
            if nums[i] > target and (nums[i] >=0 or target >= 0):
                break # prune the tree
            if i > 0 and nums[i] == nums[i - 1]: continue

            for j in range(i+1,n):
                if j > i+1 and nums[j] == nums[j - 1]: continue
                left = j+1
                right = n-1
                
                while left < right:
                    SUM = nums[i]+nums[j]+nums[left]+nums[right]
                    if SUM > target:
                        right -= 1
                    elif SUM < target:
                        left += 1
                    else:
                        res.append([nums[i], nums[j], nums[left], nums[right]])
                        while left != right and nums[left+1] == nums[left]:
                            left += 1
                        while left != right and nums[right-1] == nums[right]:
                            right -= 1
                        left += 1
                        right -= 1
        return res