#!/usr/bin/env python3

import copy
from typing import List, Dict


class Solution:
    def wordSubsets_v2(
        self, words1: List[str], words2: List[str]
    ) -> List[str]:
        """Way too slow.Way too stupid."""
        words2_maps: List[Dict] = []
        result: List[str] = []

        def get_map(word):
            word_map: Dict[str, int] = {}
            for char in word:
                if char in word_map:
                    word_map[char] = word_map[char] + 1
                else:
                    word_map[char] = 1

            return word_map

        for word in words2:
            words2_maps.append(get_map(word))
        word_map: Dict[str, int] = {}
        for word in words1:
            for char in word:
                if char in word_map:
                    word_map[char] = word_map[char] + 1
                else:
                    word_map[char] = 1
            is_matching = True
            for word2_map in words2_maps:
                for k, v in word2_map.items():
                    if k in word_map:
                        if v <= word_map[k]:
                            pass
                        else:
                            is_matching = False
                            break
                    else:
                        is_matching = False
                        break
                if is_matching:
                    pass
                else:
                    break
            if is_matching:
                result.append(word)
            # words1_maps.append(copy.deepcopy(word_map))
            word_map = {}
            is_matching = False

        return result

    def wordSubsets(self, A: List[str], B: List[str]) -> List[str]:
        def count(word):
            ans = [0] * 26
            for c in word:
                ans[ord(c) - ord("a")] += 1
            return ans

        bmax = [0] * 26
        for b in B:
            ls = count(b)
            for i in range(26):
                bmax[i] = max(bmax[i], ls[i])

        ans = []
        for a in A:
            ls = count(a)
            for i in range(26):
                if ls[i] < bmax[i]:
                    break
            else:
                ans.append(a)
        return ans


def main():
    words1 = ["amazon", "apple", "facebook", "google", "leetcode"]
    words2 = ["e", "o"]
    words3 = ["amazon", "apple", "facebook", "google", "leetcode"]
    words4 = ["l", "e"]
    solution = Solution()
    print(solution.wordSubsets(words1, words2))
    print(solution.wordSubsets(words3, words4))


if __name__ == "__main__":
    main()