LeetCode 1002. Find Common Characters

Description

https://leetcode.com/problems/find-common-characters/

Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates).  For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.

You may return the answer in any order.

Example 1:

Input: ["bella","label","roller"]
Output: ["e","l","l"]

Example 2:

Input: ["cool","lock","cook"]
Output: ["c","o"]

Note:

  1. 1 <= A.length <= 100
  2. 1 <= A[i].length <= 100
  3. A[i][j] is a lowercase letter

Explanation

Find intersects characters between all the words, and count their minimum occurrences in words.

Python Solution

class Solution:
    def commonChars(self, A: List[str]) -> List[str]:
        
        intersect = set(A[0])
        
        for word in A[1:]:
            intersect = intersect.intersection(set(word))
        
        counter = {}
        for key in intersect:
            counter[key] = sys.maxsize
        
        for key in intersect:
            for word in A:
                counter[key] = min(counter[key], word.count(key))
        
        results = []
        for key, value in counter.items():
            for i in range(value):
                results.append(key)
            
        return results
  • Time Complexity: O(N)
  • Space Complexity: O(N)

Leave a Reply

Your email address will not be published.