关注Java领域相关技术 记录有趣的事情

LeetCode-1002. 查找常用字符

US-B.Ralph
US-B.Ralph
2020-10-14

问题地址

LeetCode每日一题/2020-10-14

LeetCode1002. 查找常用字符


问题描述

规则

  • 给定仅有小写字母组成的字符串数组 A,返回列表中的每个字符串中都显示的全部字符(包括重复字符)组成的列表。例如,如果一个字符在每个字符串中出现 3 次,但不是 4 次,则需要在最终答案中包含该字符 3 次。
  • 你可以按任意顺序返回答案。

示例

  • 示例1
输入:["bella","label","roller"]
输出:["e","l","l"]
  • 示例2
输入:["cool","lock","cook"]
输出:["c","o"]

提示:

  • 1 <= A.length <= 100
  • 1 <= A[i].length <= 100
  • A[i][j] 是小写字母

解析

解题思路

  • 统计每个字符串中字符出现次数,然后合并统计结果。

数据操作分析

复杂度分析

  1. 时间复杂度
  2. 空间复杂度

编码实现

public class LeetCode1002_FindCommonCharacters {
    public List<String> commonChars(String[] A) {
        List<String> ans = new ArrayList<>();
        if (A == null || A.length == 0) return ans;

        Map<Character, Integer> selectTable = new HashMap<>();
        //统计第一个字符串的字符作为比较基准
        for (Character c : A[0].toCharArray()) selectTable.put(c, selectTable.getOrDefault(c, 0) + 1);

        //统计其他字符串中字符出现的次数
        for (int i = 1; i < A.length; i++) {
            char[] tmp = A[i].toCharArray();
            Map<Character, Integer> map = new HashMap<>();
            for (int j = 0; j < tmp.length; j++) {
                Character key = tmp[j];
                //合并统计结果
                if (selectTable.containsKey(key)) {
                    map.put(key, Math.min(selectTable.get(key), map.getOrDefault(key, 0) + 1));
                }
            }
            selectTable = map;
        }
        //map的统计结果转为list
        for (Character key : selectTable.keySet()) {
            int val = selectTable.get(key);
            for (int i = 0; i < val; i++) {
                ans.add(String.valueOf(key));
            }
        }
        return ans;
    }
}

官方解法

方法一:计数

思路与算法:

  • 根据题目的要求,如果字符 c 在所有字符串中均出现了 k 次及以上,那么最终答案中需要包含 kc。因此,我们可以使用 \textit{minfreq}[c] 存储字符 c 在所有字符串中出现次数的最小值。
  • 我们可以依次遍历每一个字符串。当我们遍历到字符串 s 时,我们使用 \textit{freq}[c] 统计 s 中每一个字符 c 出现的次数。在统计完成之后,我们再将每一个 \textit{minfreq}[c] 更新为其本身与 \textit{freq}[c] 的较小值。这样一来,当我们遍历完所有字符串后,\textit{minfreq}[c] 就存储了字符 c 在所有字符串中出现次数的最小值。

复杂度分析:

  1. 时间复杂度:O(n(m+∣Σ∣)),其中 n 是数组 A 的长度(即字符串的数目),m 是字符串的平均长度,\Sigma 为字符集,在本题中字符集为所有小写字母,|\Sigma|=26
    • 遍历所有字符串并计算 \textit{freq} 的时间复杂度为 O(nm);
    • 使用 \textit{freq} 更新 \textit{minfreq} 的时间复杂度为 O(n|\Sigma|)
    • 由于最终答案包含的字符个数不会超过最短的字符串长度,因此构造最终答案的时间复杂度为 O(m+|\Sigma|)。这一项在渐进意义上小于前二者,可以忽略。
  2. 空间复杂度:O(∣Σ∣),这里只计算存储答案之外的空间。我们使用了数组 \textit{freq}\textit{minfreq},它们的长度均为 |\Sigma|

编码实现

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;
    }
}

精彩评论

跳转地址1:1002. 查找常用字符:【哈希法经典应用】详解

思路

  • 这道题意一起就有点绕,不是那么容易懂,其实就是26个小写字符中有字符 在所有字符串里都出现的话,就输出,重复的也算。例如:
输入:["ll","ll","ll"]
输出:["l","l"]
  • 这道题目一眼看上去,就是用哈希法,“小写字符”,“出现频率”, 这些关键字都是为哈希法量身定做的啊
    • 首先可以想到的是暴力解法,一个字符串一个字符串去搜,时间复杂度是O(n^m),n是字符串长度,m是有几个字符串。
    • 可以看出这是指数级别的时间复杂度,非常高,而且代码实现也不容易,因为要统计 重复的字符,还要适当的替换或者去重。
    • 那我们还是哈希法吧。如果对哈希法不了解,可以这这篇文章:关于哈希表,你该了解这些!。
    • 如果对用数组来做哈希法不了解的话,可以看这篇:哈希表:可以拿数组当哈希表来用,但哈希值不要太大。
  • 了解了哈希法,理解了数组在哈希法中的应用之后,可以来看解题思路了。
  • 整体思路就是统计出搜索字符串里26个字符的出现的频率,然后取每个字符频率最小值,最后转成输出格式就可以了。如图:
  • 先统计第一个字符串所有字符出现的次数,代码如下:
int hashOtherStr[26] = {0}; // 统计除第一个字符串外字符的出现频率
for (int i = 1; i < A.size(); i++) {
    memset(hashOtherStr, 0, 26 * sizeof(int));
    for (int j = 0; j < A[i].size(); j++) {
        hashOtherStr[A[i][j] - 'a']++;
    }
    // 这是关键所在
    for (int k = 0; k < 26; k++) { // 更新hash,保证hash里统计26个字符在所有字符串里出现的最小次数
        hash[k] = min(hash[k], hashOtherStr[k]);
    }
}
  • 此时hash里统计着字符在所有字符串里出现的最小次数,那么把hash转正题目要求的输出格式就可以了。代码如下:
// 将hash统计的字符次数,转成输出形式
for (int i = 0; i < 26; i++) {
    while (hash[i] != 0) { // 注意这里是while,多个重复的字符
        string s(1, i + 'a'); // char -> string
        result.push_back(s);
        hash[i]--;
    }
}
编码实现
class Solution {
public:
    vector<string> commonChars(vector<string>& A) {
        vector<string> result;
        if (A.size() == 0) return result;
        int hash[26] = {0}; // 用来统计所有字符串里字符出现的最小频率
        for (int i = 0; i < A[0].size(); i++) { // 用第一个字符串给hash初始化
            hash[A[0][i] - 'a']++;
        }

        int hashOtherStr[26] = {0}; // 统计除第一个字符串外字符的出现频率
        for (int i = 1; i < A.size(); i++) {
            memset(hashOtherStr, 0, 26 * sizeof(int));
            for (int j = 0; j < A[i].size(); j++) {
                hashOtherStr[A[i][j] - 'a']++;
            }
            // 更新hash,保证hash里统计26个字符在所有字符串里出现的最小次数
            for (int k = 0; k < 26; k++) { 
                hash[k] = min(hash[k], hashOtherStr[k]);
            }
        }
        // 将hash统计的字符次数,转成输出形式
        for (int i = 0; i < 26; i++) {
            while (hash[i] != 0) { // 注意这里是while,多个重复的字符
                string s(1, i + 'a'); // char -> string
                result.push_back(s);
                hash[i]--;
            }
        }

        return result;
    }
};
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

2 × 2 =