【力扣·每日一题】2085.统计出现过一次的公共字符串（模拟 哈希表 优化 C++ Go）

题目链接

题意

给你两个字符串数组 words1 和 words2 ，请你返回在两个字符串数组中 都恰好出现一次 的字符串的数目。
输入：words1 = [“leetcode”,“is”,“amazing”,“as”,“is”], words2 = [“amazing”,“leetcode”,“is”]
输出：2
解释：

• “leetcode” 在两个数组中都恰好出现一次，计入答案。
• “amazing” 在两个数组中都恰好出现一次，计入答案。
• “is” 在两个数组中都出现过，但在 words1 中出现了 2 次，不计入答案。
• “as” 在 words1 中出现了一次，但是在 words2 中没有出现过，不计入答案。
  所以，有 2 个字符串在两个数组中都恰好出现了一次。
  提示：

$1<=words1.length,words2.length<=1000$
$1<=words1[i].length,words2[j].length<=30$
$words1[i]$ 和 $words2[j]$ 都只包含小写英文字母。

思路1

• 用哈希表mp1来统计word1中每个字符串的出现次数
• 用哈希表mp2来统计word2中每个字符串的出现次数
• 遍历哈希表mp1，判断它在word1,word2中的出现次数是否都是1，如果都是1的话，记录答案
• 时间复杂度为$O(n+m)$，空间复杂度为$O(n+m)$，其中$n$为word1里所有字符串的长度和，$m$为word2里所有字符串的长度和

代码1

golang版本代码

func countWords(words1 []string, words2 []string) int {
	mp1 := make(map[string]int, len(words1))
	mp2 := make(map[string]int, len(words2))
	for _, word := range words1 {
		mp1[word]++
	}
	for _, word := range words2 {
		mp2[word]++
	}
	var ans = 0
	for k, v := range mp1 {
		if v != 1 {
			continue
		}
		if cnt, ok := mp2[k]; ok && cnt == 1 {
			ans++
		}
	}
	return ans
}

c++版本代码

class Solution {
	public:
		int countWords(vector<string>& words1, vector<string>& words2) {
			map<string,int>mp1,mp2;
			for(auto word:words1) {
				mp1[word]++;
			}
			for(auto word:words2) {
				mp2[word]++;
			}
			int ans = 0;
			for(auto it:mp1) {
				if (it.second == 1 && mp2[it.first] == 1) {
					ans++;
				}
			}
			return ans;
		}
};

思路2

• 基于思路1的基础上，考虑能否只用一个哈希表完成题目
• 先用哈希表mp来统计word1中每个字符串的出现次数
• 遍历word2的字符串word，对mp[word]的情况进行讨论
  • mp[word]=1 说明word在word1里出现了一次，更新答案，且将mp[word]赋值为一个特殊的数字，这里赋值为-1
  • mp[word]=-1说明word在word2里已经出现了一次，当前是第二次，更新答案（这里是ans--，因为word已经不符合条件了），且将mp[word]赋值为正常的计数2
• 看了下运行截图还是优化了下空间的

代码2

golang版本代码

func countWords(words1 []string, words2 []string) int {
	mp := make(map[string]int, len(words1))
	for _, word := range words1 {
		mp[word]++
	}
	var ans = 0
	for _, word := range words2 {
		switch mp[word] {
		case 1:
			ans++
			mp[word] = -1
		case -1:
			ans--
			mp[word] = 2
		}
	}
	return ans
}

c++版本代码

class Solution {
	public:
		int countWords(vector<string>& words1, vector<string>& words2) {
			map<string,int>mp;
			for(auto word:words1) {
				mp[word]++;
			}
            int ans = 0;
			for(auto word:words2) {
				if(mp[word]==1) {
					mp[word] = -1;
					ans ++;
				} else if(mp[word]==-1) {
					mp[word] = 2;
					ans --;
				}
			}
			return ans;
		}
};