Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/1002.html

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 <= A.length <= 100
1 <= A[i].length <= 100
A[i][j] is a lowercase letter

Algorithm

This question gives a set of strings composed of lowercase letters, so that all the same characters in the string are returned, and the repeated characters must appear the corresponding number of times. In fact, the core of this question is how to judge the intersecting part of the string, which is similar to the previous Intersection of Two Arrays II and Intersection of Two Arrays.

The core is to use HashMap to establish a mapping between characters and their occurrences. Since there are only lowercase letters here, an array of size 26 can be used instead of HashMap. Use an array cnt to record the number of occurrences of the same letter, initialize it to the maximum value of the integer, and then traverse all the words. For each word, create a new array t of size 26, and count the number of occurrences of each character, then Traverse the positions from 0 to 25, take the smaller value of the corresponding positions of cnt and t to update the cnt array, so that the number of letters that appear in all words is obtained, and finally these characters are converted into strings and added to the result In res, see the code as follows:

Code

C++

```cppclass Solution { public: vector commonChars(vector& A) { vector res; vector cnt(26, INT_MAX); for (string word : A) { vector t(26); for (char c : word) ++t[c - 'a']; for (int i = 0; i < 26; ++i) { cnt[i] = min(cnt[i], t[i]); } } for (int i = 0; i < 26; ++i) { for (int j = 0; j < cnt[i]; ++j) { res.push_back(string(1, 'a' + i)); } } return res; } };

```

  • class Solution {
    public List<String> commonChars(String[] A) {
        int[] countsIntersection = new int[26];
        for (int i = 0; i < 26; i++)
            countsIntersection[i] = Integer.MAX_VALUE;
        for (String str : A) {
            int[] counts = new int[26];
            char[] array = str.toCharArray();
            for (char c : array)
                counts[c - 'a']++;
            for (int i = 0; i < 26; i++)
                countsIntersection[i] = Math.min(countsIntersection[i], counts[i]);
        }
        List<String> letters = new ArrayList<String>();
        for (int i = 0; i < 26; i++) {
            String curLetter = String.valueOf((char) ('a' + i));
            int curCount = countsIntersection[i];
            for (int j = 0; j < curCount; j++)
                letters.add(curLetter);
        }
        return letters;
    }
}

  • // OJ: https://leetcode.com/problems/find-common-characters/
// Time: O(C) where C is the size of all the contents in A
// Space: O(1)
class Solution {
public:
    vector<string> commonChars(vector<string>& A) {
        vector<int> overlap(26, INT_MAX);
        for (string s : A) {
            vector<int> cnt(26, 0);
            for (char c : s) cnt[c - 'a']++;
            for (int i = 0; i < 26; ++i) overlap[i] = min(overlap[i], cnt[i]);
        }
        vector<string> ans;
        for (int i = 0; i < 26; ++i) {
            while (overlap[i]--) ans.push_back(string(1, 'a' + i));
        }
        return ans;
    }
};

  • class Solution:
    def commonChars(self, words: List[str]) -> List[str]:
        freq = [10000] * 26
        for word in words:
            t = [0] * 26
            for c in word:
                t[ord(c) - ord('a')] += 1
            for i in range(26):
                freq[i] = min(freq[i], t[i])
        res = []
        for i in range(26):
            if freq[i] > 0:
                res.extend([chr(i + ord("a"))] * freq[i])
        return res

############

class Solution(object):
    def commonChars(self, A):
        """
        :type A: List[str]
        :rtype: List[str]
        """
        A_count = map(lambda x : collections.Counter(x), A)
        res = []
        for i in range(26):
            c = chr(ord('a') + i)
            min_count = min([a_count[c] for a_count in A_count])
            if min_count:
                res.extend([c] * min_count)
        return res

All Problems

All Solutions