LeetCode 2085.统计出现过一次的公共字符串:哈希表

2024-01-13 16:20

本文主要是介绍LeetCode 2085.统计出现过一次的公共字符串:哈希表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【LetMeFly】2085.统计出现过一次的公共字符串:哈希表

力扣题目链接:https://leetcode.cn/problems/count-common-words-with-one-occurrence/

给你两个字符串数组 words1 和 words2 ,请你返回在两个字符串数组中 都恰好出现一次 的字符串的数目。

 

示例 1:

输入:words1 = ["leetcode","is","amazing","as","is"], words2 = ["amazing","leetcode","is"]
输出:2
解释:
- "leetcode" 在两个数组中都恰好出现一次,计入答案。
- "amazing" 在两个数组中都恰好出现一次,计入答案。
- "is" 在两个数组中都出现过,但在 words1 中出现了 2 次,不计入答案。
- "as" 在 words1 中出现了一次,但是在 words2 中没有出现过,不计入答案。
所以,有 2 个字符串在两个数组中都恰好出现了一次。

示例 2:

输入:words1 = ["b","bb","bbb"], words2 = ["a","aa","aaa"]
输出:0
解释:没有字符串在两个数组中都恰好出现一次。

示例 3:

输入:words1 = ["a","ab"], words2 = ["a","a","a","ab"]
输出:1
解释:唯一在两个数组中都出现一次的字符串是 "ab" 。

 

提示:

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

方法一:哈希表

使用两个哈希表,分别统计两个字符串数组中,每个字符串出现的次数。

(这样,对于一个字符串,我们就能在 O ( 1 ) O(1) O(1)的时间复杂度内得到这个字符串在两个字符串数组中出现的次数。)

遍历其中一个哈希表,如果这个字符串在两个哈希表中出现的次数都为 1 1 1,则答案个数 + 1 +1 +1

  • 时间复杂度 O ( s i z e ( w o r d s 1 ) + s i z e ( w o r d s 2 ) ) O(size(words1) + size(words2)) O(size(words1)+size(words2)),其中 s i z e ( w o r d s i ) size(words_i) size(wordsi)为字符串数组 w o r d s i words_i wordsi的字符个数。
  • 空间复杂度 O ( s i z e ( w o r d s 1 ) + s i z e ( w o r d s 2 ) ) O(size(words1) + size(words2)) O(size(words1)+size(words2))

AC代码

C++
class Solution {
public:int countWords(vector<string>& words1, vector<string>& words2) {unordered_map<string, int> m1, m2;for (auto& s : words1) {m1[s]++;}for (auto& s : words2) {m2[s]++;}int ans = 0;for (auto&& [str, cnt] : m1) {if (cnt == 1 && m2[str] == 1) {ans++;}}return ans;}
};
Python
# from typing import List
# from collections import defaultdictclass Solution:def countWords(self, words1: List[str], words2: List[str]) -> int:m1, m2 = defaultdict(int), defaultdict(int)for s in words1:m1[s] += 1for s in words2:m2[s] += 1ans = 0for s, cnt in m1.items():if cnt == 1 and m2[s] == 1:ans += 1return ans

同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/135560255

这篇关于LeetCode 2085.统计出现过一次的公共字符串:哈希表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/602069

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

hdu1496(用hash思想统计数目)

作为一个刚学hash的孩子,感觉这道题目很不错,灵活的运用的数组的下标。 解题步骤:如果用常规方法解,那么时间复杂度为O(n^4),肯定会超时,然后参考了网上的解题方法,将等式分成两个部分,a*x1^2+b*x2^2和c*x3^2+d*x4^2, 各自作为数组的下标,如果两部分相加为0,则满足等式; 代码如下: #include<iostream>#include<algorithm

poj1330(LCA最近公共祖先)

题意:求最近公共祖先 思路:之前学习了树链剖分,然后我就用树链剖分的一小部分知识就可以解这个题目了,记录每个结点的fa和depth。然后查找时,每次将depth大的结点往上走直到x = y。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

flume系列之:查看flume系统日志、查看统计flume日志类型、查看flume日志

遍历指定目录下多个文件查找指定内容 服务器系统日志会记录flume相关日志 cat /var/log/messages |grep -i oom 查找系统日志中关于flume的指定日志 import osdef search_string_in_files(directory, search_string):count = 0

hdu4267区间统计

题意:给一些数,有两种操作,一种是在[a,b] 区间内,对(i - a)% k == 0 的加value,另一种操作是询问某个位置的值。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import

hdu4417区间统计

给你一个数列{An},然后有m次查询,每次查询一段区间 [l,r] <= h 的值的个数。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamRead

hdu3333区间统计

题目大意:求一个区间内不重复数字的和,例如1 1 1 3,区间[1,4]的和为4。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;