题目链接

题意

给你两个字符串数组 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 = 0for 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 = 0for _, word := range words2 {switch mp[word] {case 1:ans++mp[word] = -1case -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;}
};