23.02.09 Today’s Leetcode

2306. Naming a Company (hard)

첫번째 Solution : O(n^2)

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        idea_ = set(ideas)
        n = len(ideas)
        res = 0
        for i in range(n):
            for j in range(n):
                a, b = ideas[i], ideas[j]
                a_, b_ = b[0] + a[1:], a[0] + b[1:]
                if a_ in idea_ or b_ in idea_:
                    continue
                else:
                    res += 1
                # print(a_, b_)
        return res

두번째 Solution : O(n^2), group with same first letters 교집합을 이용한 풀이.

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        # Group idea by their initials.
        initial_groups = [set() for _ in range(26)]
        for idea in ideas:
            initial_groups[ord(idea[0]) - ord('a')].add(idea[1:])
        
        answer = 0
        # Calculate number of valid names from every pair of groups.
        for i in range(25):
            for j in range(i + 1, 26):
                # Get the number of mutual suffixes.
                num_of_mutual = len(initial_groups[i] & initial_groups[j]) 
                
                # Valid names are only from distinct suffixes in both groups.
                # Since we can swap a with b and swap b with a to create two valid names, multiple answer by 2.
                answer += 2 * (len(initial_groups[i]) - num_of_mutual) * (len(initial_groups[j]) - num_of_mutual)
                
        return answer

350. Intersection of Two Arrays II (easy)

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        a, b = Counter(nums1), Counter(nums2)
        res = []
        for key in a.keys() & b.keys():
            for i in range(min(a[key], b[key])):
                res.append(key)
        return res

121. Best Time to Buy and Sell Stock (easy)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        local_max = prices[0]
        local_min = prices[0]
        res = 0
        for price in prices:
            if price < local_min:
                local_min = price
                local_max = price
            
            local_max = max(local_max, price)
            res = max(res, local_max - local_min)
        return res