https://leetcode.com/problems/find-common-characters/
https://leetcode.com/problems/find-common-characters/discuss/247573/C%2B%2B-O(n)-or-O(1)-two-vectors
https://leetcode.com/problems/find-common-characters/discuss/247558/Java-15-liner-count-and-look-for-minimum.
X. https://leetcode.com/problems/find-common-characters/discuss/247637/Java-Two-HashMap-Solution-Easy-To-Understand
X. https://leetcode.com/problems/find-common-characters/discuss/247710/Java-Solution-%3A-Using-Map
We can use iterator to remove
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
https://leetcode.com/problems/find-common-characters/discuss/247573/C%2B%2B-O(n)-or-O(1)-two-vectors
For each string, we count characters in
cnt1
. Then, we track the minimum count cnt
.vector<string> commonChars(vector<string>& A) {
vector<int> cnt(26, INT_MAX);
vector<string> res;
for (auto s : A) {
vector<int> cnt1(26, 0);
for (auto c : s) ++cnt1[c - 'a'];
for (auto i = 0; i < 26; ++i) cnt[i] = min(cnt[i], cnt1[i]);
}
for (auto i = 0; i < 26; ++i)
for (auto j = 0; j < cnt[i]; ++j) res.push_back(string(1, i + 'a'));
return res;
}
Complexity Analysis
Runtime: O(n), where n is the total number of characters.
https://leetcode.com/problems/find-common-characters/discuss/247558/Java-15-liner-count-and-look-for-minimum.
Initialize
count
array with Integer.MAX_VALUE
, loop through the input to count the chars in each string; then find out the minimum for each char. public List<String> commonChars(String[] A) {
List<String> ans = new ArrayList<>();
int[] count = new int[26];
Arrays.fill(count, Integer.MAX_VALUE);
for (String a : A) {
int[] t = new int[26];
for (char c : a.toCharArray()) { ++t[c - 'a']; }
for (int i = 0; i < 26; ++i) {
count[i] = Math.min(t[i], count[i]);
}
}
for (int i = 0; i < 26; ++i) {
if (count[i] == Integer.MAX_VALUE) continue;
while (count[i]-- > 0) { ans.add("" + (char)(i + 'a')); }
}
return ans;
}
X. https://leetcode.com/problems/find-common-characters/discuss/247637/Java-Two-HashMap-Solution-Easy-To-Understand
The idea here is to use two HashMaps. The first, which we call
union
, will contain all of the common chars found in the strings compared before our current string. Then, before we go through the chars in the current string, we declare a new HashMap, called temp
. temp
will contain the chars that are found in our current string which are also found in union
.
We have to make sure that we don't add a common char too many times. For example, if we have 2 instances of the letter
c
in common strings before the current, but we have three instances of c
in the current string, we have to make sure that we only count 2 instances of c
in common.
We do this via the following line:
Math.min(union.get(curr), temp.getOrDefault(curr, 0)+1)
. Then, when we finish looping through the current string, we just set union
to temp
. List<String> ans = new ArrayList<String>();
if(A == null || A.length == 0) return ans;
HashMap<Character, Integer> union = new HashMap<>();
for(int i = 0; i < A[0].length(); i++) union.put(A[0].charAt(i), union.getOrDefault(A[0].charAt(i), 0)+1);
for(int i = 1; i < A.length; i++){
HashMap<Character, Integer> temp = new HashMap<>();
for(int j = 0; j < A[i].length(); j++){
char curr = A[i].charAt(j);
if(union.containsKey(curr)) temp.put(curr, Math.min(union.get(curr), temp.getOrDefault(curr, 0)+1));
}
union = temp;
}
for(char c : union.keySet()){
for(int i = 0; i < union.get(c); i++) ans.add(c + "");
}
return ans;
X. https://leetcode.com/problems/find-common-characters/discuss/247710/Java-Solution-%3A-Using-Map
We can use iterator to remove
List result = new ArrayList<>();
String word = A[0];
Map<Character, Integer> common = getChars(word);
for(int i=1; i < A.length; i++){
Map<Character, Integer> chars = getChars(A[i]);
Set<Character> keysToDelete = new HashSet<>();
for(Character c : common.keySet()){
if(chars.containsKey(c)){
if(chars.get(c) < common.get(c)){
common.put(c, chars.get(c));
}
}else{
keysToDelete.add(c);
}
}
for(Character c : keysToDelete){
common.remove(c);
}
}
for(Character c : common.keySet()){
int length = common.get(c);
for(int i=0; i < length; i++){
result.add(Character.toString(c));
}
}
return result;
}
private Map<Character, Integer> getChars(String word) {
Map<Character, Integer> map = new HashMap<>();
for(char c : word.toCharArray()){
map.put(c, map.getOrDefault(c, 0) + 1);
}
return map;
}