題目鏈接

題意

給你兩個(gè)字符串?dāng)?shù)組 words1 和 words2 ，請(qǐng)你返回在兩個(gè)字符串?dāng)?shù)組中 都恰好出現(xiàn)一次 的字符串的數(shù)目。
輸入：words1 = [“l(fā)eetcode”,“is”,“amazing”,“as”,“is”], words2 = [“amazing”,“l(fā)eetcode”,“is”]
輸出：2
解釋：

• “l(fā)eetcode” 在兩個(gè)數(shù)組中都恰好出現(xiàn)一次，計(jì)入答案。
• “amazing” 在兩個(gè)數(shù)組中都恰好出現(xiàn)一次，計(jì)入答案。
• “is” 在兩個(gè)數(shù)組中都出現(xiàn)過，但在 words1 中出現(xiàn)了 2 次，不計(jì)入答案。
• “as” 在 words1 中出現(xiàn)了一次，但是在 words2 中沒有出現(xiàn)過，不計(jì)入答案。
  所以，有 2 個(gè)字符串在兩個(gè)數(shù)組中都恰好出現(xiàn)了一次。
  提示：

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

思路1

• 用哈希表mp1來統(tǒng)計(jì)word1中每個(gè)字符串的出現(xiàn)次數(shù)
• 用哈希表mp2來統(tǒng)計(jì)word2中每個(gè)字符串的出現(xiàn)次數(shù)
• 遍歷哈希表mp1，判斷它在word1,word2中的出現(xiàn)次數(shù)是否都是1，如果都是1的話，記錄答案
• 時(shí)間復(fù)雜度為$O(n+m)$，空間復(fù)雜度為$O(n+m)$，其中$n$為word1里所有字符串的長(zhǎng)度和，$m$為word2里所有字符串的長(zhǎng)度和

代碼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的基礎(chǔ)上，考慮能否只用一個(gè)哈希表完成題目
• 先用哈希表mp來統(tǒng)計(jì)word1中每個(gè)字符串的出現(xiàn)次數(shù)
• 遍歷word2的字符串word，對(duì)mp[word]的情況進(jìn)行討論
  • mp[word]=1 說明word在word1里出現(xiàn)了一次，更新答案，且將mp[word]賦值為一個(gè)特殊的數(shù)字，這里賦值為-1
  • mp[word]=-1說明word在word2里已經(jīng)出現(xiàn)了一次，當(dāng)前是第二次，更新答案（這里是ans--，因?yàn)?code>word已經(jīng)不符合條件了），且將mp[word]賦值為正常的計(jì)數(shù)2
• 看了下運(yùn)行截圖還是優(yōu)化了下空間的

代碼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++版本代碼

文章來源地址http://www.zghlxwxcb.cn/news/detail-812614.html

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

到了這里，關(guān)于【力扣·每日一題】2085.統(tǒng)計(jì)出現(xiàn)過一次的公共字符串（模擬 哈希表 優(yōu)化 C++ Go）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！