Leetcode-771 Jewels and Stones

Description

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

1
2
Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

1
2
Input: J = "z", S = "ZZ"
Output: 0

Note:

  • S and J will consist of letters and have length at most 50.
  • The characters in J are distinct.

分析

给定两个字符串 JSJ 代表珠宝类型,S 代表石头类型,在 S 中找出珠宝的个数。其中给定的字符串长度不超过 50,J 中的字符不重复。

最简单的想法是使用 Hash 存储 J 中的字符,然后遍历 S 中的每个字符,如果字符命中 Hash,则珠宝数量加 1。这种做法时间复杂度 O(n),空间复杂度 O(n),实现也简单,我看可行。

程序设计

按照上述分析思路,使用 Python 实现如下,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def numJewelsInStones(self, J: str, S: str) -> int:
if len(S) == 0 or len(J) == 0:
return 0

jewels = 0
char_map = dict()

for j in J:
char_map[j] = True

for s in S:
if char_map.get(s):
jewels += 1

return jewels

提交,也能 bugfree,但是 ac 结果显示内存使用打败 5.33% 的 Python 提交。如果要优化空间复杂度的花,可以使用一个长度为 128 的整型数组保存宝石的类型, Java 实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int numJewelsInStones(String J, String S) {
if (J.length() == 0 || S.length() == 0) {
return 0;
}

int jewels = 0;
int[] types = new int[128];

for (char c: J.toCharArray()) {
types[c-0] = 1;
}

for (char c: S.toCharArray()) {
jewels += types[c-0];
}

return jewels;
}
}

提交后,时空复杂度都还可以。

本文标题:Leetcode-771 Jewels and Stones

文章作者:Syncher

发布时间:2019年07月22日 - 09:07

最后更新:2019年10月10日 - 18:10

原始链接:https://0x400.com/2019-07-22-lc-771-jewels-and-stones.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。