Description
Given a string array words, return an array of all characters that show up in all strings within the words (including duplicates). You may return the answer in any order.
Example 1:
Input: words = ["bella","label","roller"]
Output: ["e","l","l"]
Example 2:
Input: words = ["cool","lock","cook"]
Output: ["c","o"]
Constraints:
1 <= words.length <= 1001 <= words[i].length <= 100words[i] consists of lowercase English letters.
Solutions
Solution 1: Counting
We use an array cnt of length 26 to record the minimum number of times each character appears in all strings. Finally, we traverse the cnt array and add characters with a count greater than 0 to the answer.
The time complexity is O(n ∑ wi), and the space complexity is O(|Σ|). Here, n is the length of the string array words, wi is the length of the i-th string in the array words, and |Σ| is the size of the character set, which is 26 in this problem.
PythonJavaC++GoTypeScript
class Solution:
def commonChars(self, words: List[str]) -> List[str]:
cnt = Counter(words[0])
for w in words:
t = Counter(w)
for c in cnt:
cnt[c] = min(cnt[c], t[c])
return list(cnt.elements())(code-box)
class Solution {
public List<String> commonChars(String[] words) {
int[] cnt = new int[26];
Arrays.fill(cnt, 20000);
for (var w : words) {
int[] t = new int[26];
for (int i = 0; i < w.length(); ++i) {
++t[w.charAt(i) - 'a'];
}
for (int i = 0; i < 26; ++i) {
cnt[i] = Math.min(cnt[i], t[i]);
}
}
List<String> ans = new ArrayList<>();
for (int i = 0; i < 26; ++i) {
ans.addAll(Collections.nCopies(cnt[i], String.valueOf((char) ('a' + i))));
}
return ans;
}
}(code-box)
class Solution {
public:
vector<string> commonChars(vector<string>& words) {
vector<int> cnt(26, 20000);
for (const auto& w : words) {
vector<int> t(26, 0);
for (char c : w) {
++t[c - 'a'];
}
for (int i = 0; i < 26; ++i) {
cnt[i] = min(cnt[i], t[i]);
}
}
vector<string> ans;
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < cnt[i]; ++j) {
ans.push_back(string(1, 'a' + i));
}
}
return ans;
}
};(code-box)
func commonChars(words []string) (ans []string) {
cnt := make([]int, 26)
for i := range cnt {
cnt[i] = 20000
}
for _, w := range words {
t := make([]int, 26)
for _, c := range w {
t[c-'a']++
}
for i := 0; i < 26; i++ {
cnt[i] = min(cnt[i], t[i])
}
}
for i := 0; i < 26; i++ {
for j := 0; j < cnt[i]; j++ {
ans = append(ans, string('a'+rune(i)))
}
}
return ans
}(code-box)
function commonChars(words: string[]): string[] {
const cnt = Array(26).fill(20000);
const aCode = 'a'.charCodeAt(0);
for (const w of words) {
const t = Array(26).fill(0);
for (const c of w) {
t[c.charCodeAt(0) - aCode]++;
}
for (let i = 0; i < 26; i++) {
cnt[i] = Math.min(cnt[i], t[i]);
}
}
const ans: string[] = [];
for (let i = 0; i < 26; i++) {
cnt[i] && ans.push(...String.fromCharCode(i + aCode).repeat(cnt[i]));
}
return ans;
}(code-box)
