771. Jewels and Stones

Posted on Edited on In

711. Jewels and Stones

题目

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中查找，发现要用两个for循环，复杂度太高，就在想怎么只用一个循环，就想到了count方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def numJewelsInStones(self, J, S):
        """
        :type J: str
        :type S: str
        :rtype: int
        """
        sum = 0
        for j in J:
            count = S.count(j)
            sum += count 
        return sum
# Runtime: 12 ms
# Memory Usage: 11.9 MB

从答案中找到了一些很简洁的解决办法：

1
2
3
4
5
6
7
8
9
def numJewelsInStones(self, J, S):
    return sum(map(J.count, S))
def numJewelsInStones(self, J, S):
    return sum(map(S.count, J))               
def numJewelsInStones(self, J, S):
    return sum(s in J for s in S)
def numJewelsInStones(self, J, S):
    J = set(J)
    return sum([1 for stone in S if stone in J])

但是似乎运行时间和内存占用比不比我第一次提交的代码小。

总结

  1. 代码的简洁度固然重要，但是Time and space complexity（时空复杂度）应该排在第一位。
  2. map函数
1
map(function, iterable, ...)

map() 会根据提供的函数对指定序列做映射。第一个参数 function 以参数序列中的每一个元素调用 function 函数，返回包含每次 function 函数返回值的新列表。

  1. count函数
1
str.count(sub, start= 0,end=len(string))
  • sub – 搜索的子字符串
  • start – 字符串开始搜索的位置。默认为第一个字符,第一个字符索引值为0。
  • end – 字符串中结束搜索的位置。字符中第一个字符的索引为 0。默认为字符串的最后一个位置。

注意：c

1
2
3
4
>>> st1 = "ADA"
>>> st2 = "ADADADA"
>>> st2.count(st1)
2
  1. Python中函数带括号和不带括号的区别
  • 不带括号时，调用的是这个函数本身 ，是整个函数体，是一个函数对象，不需等该函数执行完成
  • 带括号时（此时必须传入需要的参数），调用的是函数的return结果，需要等待函数执行完成的结果

所以：

map(J.count, S)和map(S.count, J)分别代表在J中查找S中的元素的个数和在S中查找J中元素的个数。

  1. sum(s in J for s in S)使用了生成器（genexps），将S中的原色进行了过滤，对S中的元素依次判断它是否在J中。

References

Python中函数带括号和不带括号的区别