LeetCode日记— 1002. Find Common Characters

发布于 2020-10-14  116 次阅读


碎碎念:妈的笔记本又充不进去电了,日了。。画这么多钱买了个寂寞。。。售后还疯狂踢皮球,屁事贼多。如果能重来,我一定整个轻薄本,加上一个台式机(虽然现在iPad生产力也蛮不错的hhh

题目如下:

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.

Example1:

Input: ["bella","label","roller"]
Output: ["e","l","l"]

Example2:

Input: ["cool","lock","cook"]
Output: ["c","o"]

思路:

我自己的思路,存在一个hashMap里面,key是string,value是出现的次数。然后,每次遍历一个String的时候去除掉本次未遍历的值(某个字母未在任意一个string中出现则说明不可能重复出现该字母了)。但是后面发现这样要把每个String遍历两遍,效率实在是太低了。

于是参考了官方解法,官方解法中维护了一个int数组,freq【26】(大小为26的原因是题目已经说明了只有小写字母),每次存入某个字母在当前String遍历时出现的频率,再维护一个minfreq数组,最后用minfreq数组完成返回List的构建。

代码如下

class Solution {
    public List<String> commonChars(String[] A) {
        int[] minfreq = new int[26];
        Arrays.fill(minfreq, Integer.MAX_VALUE);
        for (String word: A) {
            int[] freq = new int[26];
            int length = word.length();
            for (int i = 0; i < length; ++i) {
                char ch = word.charAt(i);
                ++freq[ch - 'a'];
            }
            for (int i = 0; i < 26; ++i) {
                minfreq[i] = Math.min(minfreq[i], freq[i]);
            }
        }

        List<String> ans = new ArrayList<String>();
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < minfreq[i]; ++j) {
                ans.add(String.valueOf((char) (i + 'a')));
            }
        }
        return ans;
    }
}


你好哇!欢迎来到雷公马碎碎念的地方:)