771. 宝石与石头
2020-09-05 本文已影响0人
一角钱技术
771. 宝石与石头
给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。<br />
<br />J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。
示例 1:
输入: J = "aA", S = "aAAbbbb"
输出: 3
示例 2:
输入: J = "z", S = "ZZ"
输出: 0
注意:
- S 和 J 最多含有50个字母。
- J 中的字符不重复。
审题
题目的以上 J 代表宝石的类型，也就是说 J 每个字符是一个类型，S 代表你拥有的石头， S中每个字符代表石头的类型，问你在这堆石头中有多少个是宝石。也就是 J 每个字符 在 S 中存在的字符数有多少。注意：区分大小写，且 J 不重复。
方法1: 暴力法
算法思路：
遍历每块石头，检查是不是宝石，两层循环，检查步骤用简单的线性搜索来实现。
参考代码1:
class Solution {
public int numJewelsInStones1(String J, String S) {
int res = 0;
for (int i = 0; i < S.length(); i++) {
for (int j = 0; j < J.length(); j++) {
if (S.charAt(i) == J.charAt(j)) {
res++;
break;
}
}
}
return res;
}
}
复杂度分析:
- 时间复杂度：
。
- 空间复杂度：
方法2: 哈希集合
算法思路：
把宝石存入哈希集合中，遍历每块石头，用哈希集合来高效检查是不是宝石。
参考代码2:
class Solution {
public int numJewelsInStones2(String J, String S) {
int res = 0;
Set<Character> set = new HashSet<>();
for (char ch : J.toCharArray()) {
set.add(ch);
}
for (char ch : S.toCharArray()) {
if (set.contains(ch)) {
res++;
}
}
return res;
}
}
复杂度分析:
- 时间复杂度：
。
- 空间复杂度：
。
方法3: ASCII码
算法思路：
考虑更高的空间性能，使用 int 数组， ASCII 码中字母的跨度为 65 ～ 122，所以定义数组的长度为 58 最节省。
a-z：97-122
A-Z：65-90
0-9：48-57
参考代码3:
class Solution {
public int numJewelsInStones(String J, String S) {
int res = 0;
int[] words = new int[58];
for (char ch : J.toCharArray()) {
words[ch - 65]++;
}
for (char ch : S.toCharArray()) {
if (words[ch - 65] == 1) {
res++;
}
}
return res;
}
}
复杂度分析:
- 时间复杂度：
- 空间复杂度：
。只用到了58个常数的空间长度。
方法4: 正则表达式
参考代码4:
class Solution {
public int numJewelsInStones(String J, String S) {
String a = "[^"+J+']';
S = S.replaceAll(a, "");
return S.length();
}
}
以上谢谢大家，求赞求赞求赞！
