Leetcode-771 Jewels and Stones

Posted on Edited on In ,

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.

分析

给定两个字符串 J 和 S， J 代表珠宝类型，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;
    }
}

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