题目:https://leetcode-cn.com/problems/find-common-characters/
代码:
class Solution {
public List<String> commonChars(String[] A) {
//定义字母表,并填充最大值
int[] letter = new int[26];
for (int i = 0; i < letter.length; i++) {
letter[i] = Integer.MAX_VALUE;
}
//遍历A
for (int i = 0; i < A.length; i++) {
//计算i位置字符串每个字母的出现次数
int[] temp = new int[letter.length];
for (char c : A[i].toCharArray()) {
temp[c - 'a']++;
}
//保留最小值的情况
for (int j = 0; j < letter.length; j++) {
if (letter[j] > temp[j]) {
letter[j] = temp[j];
}
}
}
//返回最终结果
List<String> res = new ArrayList<>();
for (int i = 0; i < letter.length; i++) {
for (int j = 0; j < letter[i]; j++) {
res.add(String.valueOf((char)(i+'a')));
}
}
return res;
}
}
因为A仅包含小写字母,所以我们可以考虑定义二维数组字母表,如图:
其中列是a-z这26个字母,每一行是一个字符串,每一个单元格表示当前列所表示的字母在当前行的字符串中出现的次数,如:A1=1则表示字母a在第一个字符串afb中出现次数为1。
按照以上思路我们遍历所有字符串,得到一个二维表,最后求每一列中的最小值。如第一列最后结果为0,则表示结果中不含a;第二列最后结果为1,则表示结果中有一个字符串为b;依次类推,最后结果为n,则表示结果中有n个字符串是c。
优化:我们可以将最后求每一列最小值的工作在遍历字符串的过程中也一并处理了,这样我们只需要一个一维数组即可实现,最终逻辑请参考代码。