【力扣算法题解】2085. 统计出现过一次的公共字符串

Problem: 2085. 统计出现过一次的公共字符串

思路

这道题我当初做的时候想的是一个HashMap用来记录单词出现次数，另一个HashMap用来去重。
比官方的题解快一个循环，不过官方的通俗易懂些。

解题方法

第一遍循环用来记录words1中不同单词出现的次数。第二遍循环是关键，在遍历到相同字符串时，如果出现的次数为1次，那么就能算作答案，cnt++，并标记这个单词在words2中出现过一次了，所以第二个HashMap用在这。否则如果出现的次数为2次，有两种情况：第一种是words1中出现过两次这种单词；第二种是word1中出现一次，words2中出现一次（这种情况还需要cnt–，因为words2出现两次了）。所以还要根据去重的HashMap来判断是否是第一种情况。

复杂度

时间复杂度:

$O(words1.length+words2.length)$

空间复杂度:

$O(words1中不同单词的数量)$

Code

class Solution {
    public int countWords(String[] words1, String[] words2) {
        HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
        HashMap<String, Boolean> hashMap2 = new HashMap<String, Boolean>();
        for(int i = 0; i < words1.length; i++) {
            hashMap.put(words1[i], hashMap.getOrDefault(words1[i], 0)+1);
        }
        int cnt = 0;
        for(int i = 0; i < words2.length; i++) {
            int num = hashMap.getOrDefault(words2[i], 0);
            if (num == 1) {
                hashMap.put(words2[i], num+1);
                hashMap2.put(words2[i], true);
                cnt++;
            } else if (num == 2 && hashMap2.getOrDefault(words2[i], false)) {
                hashMap.put(words2[i], num+1);
                cnt--;
            }
        }
        return cnt;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22