LeetCode算法题771解题思路

2019年03月15日 |

leetcode/ algorithm/ easy

| leetcode algorithm

原题

771. Jewels and Stone

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:

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

Example 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.

原题地址：https://leetcode.com/problems/jewels-and-stones/

思路

不瞒大家，读完题目后，我脑子里的第一反应是两层for循环套起走。🤦

不过紧接着我就知道这一定是错的，这种思路当然可以实现题目的需求，但是解法实在是低级。时间复杂度是 $O(n^2)$

我能那么快想到解决方法，得益于前几天看的《啊哈！算法》中的第一个算法：桶排序。

我借鉴了桶排序的思路, 迅速想到要把S中的每个字符转换成map的形式（key-value），key是字符的值，value是key在S中出现的次数。
这样可以减少统计宝石个数时所需要的循环次数。

然后通过遍历J中的字符，去map中查找数量，最后累加起来即可。

那么程序的时间复杂度就降为了 $O(n)$。

看到这里如果你已清楚思路的话，请你自己先动手实践一下，切勿直接看我的实现代码。
毕竟，实践出真知。
代码仅供参考。

代码实现

Golang实现

https://github.com/cook-coder/my-leetcode-solution/tree/master/easy/771

嘚瑟

最后请容我嘚瑟一下，贴个程序提交之后的评价图