1002-查找常用字符
文章目录
前言
给定仅有小写字母组成的字符串数组
A,返回列表中的每个字符串中都显示的全部字符(包括重复字符)组成的列表。例如,如果一个字符在每个字符串中出现3次,但不是4次,则需要在最终答案中包含该字符3次。你可以按任意顺序返回答案。
示例1:
输入:["bella","label","roller"] 输出:["e","l","l"]示例2:
输入:["cool","lock","cook"] 输出:["c","o"]提示:
1 <= A.length <= 1001 <= A[i].length <= 100A[i][j]是小写字母
解题思路
本题需要注意的是要输出所有单词中重复的字符,如果重复字符有多个就输出对应个数。我的解题思路如下:
- 以单词中的字符为
key,字符在单词中的出现次数为value的Map将每个单词的字符及出现频次记录下来。 - 找出每个
Map中key相同的元素,并以出现次数value的最小值为新的value组成重复单词出现频次的Map - 遍历步骤2中的
Map,根据value可以得知每个单词的出现次数,将Map转化为一个List
实现代码
/**
* 1002. 查找常用字符
* @param A
* @return
*/
public List<String> commonChars(String[] A) {
// 记录重复字符出现次数的map
// key为单词中的字符,value为单词中该字符的出现次数
Map<String,Integer> searchMap=new HashMap<>();
for(int i=0;i<A.length;i++){
String[] words=A[i].split("");
Map<String,Integer> map=new HashMap<>();
for(String word:words){
if(map.containsKey(word)){
map.put(word,map.get(word)+1);
}else{
map.put(word,1);
}
}
if(i==0){//第一次遍历时把所有字符和其对应的出现次数记录下来
searchMap.putAll(map);
}else{
Iterator<Map.Entry<String,Integer>> it=searchMap.entrySet().iterator();
//新的重复字符出现次数的map
Map<String,Integer> newSearchMap=new HashMap<>();
while (it.hasNext()){
Map.Entry<String,Integer> entry=it.next();
String key=entry.getKey();
Integer value=entry.getValue();
if(map.containsKey(key)){// 在原map中存在相同字符,则将其记录到新的map中,需要注意,以较少出现次数的准
Integer otherValue=map.get(key);
newSearchMap.put(key,Math.min(value,otherValue));
}
}
searchMap=newSearchMap;
}
}
List<String> result=new ArrayList<>();
searchMap.forEach((k,v)->{//将map转化为结果
for(int i=1;i<=v;i++){//根据出现次数value来给result添加对应个数的key
result.add(k);
}
});
return result;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论