771. 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:

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.

看到这个题目首先想到的是要避免过多的循环，这是一个典型的查找类型的题。

最简单最直觉的算法是，每次从J中取出一个字符，然后遍历一遍S，如果找到，就对返回结果+1

但这样的算法复杂度是：O(m*n)

我们可以把J当做一个字典，然后遍历S，看看其中的字符是否在字典内。这样就只需要遍历一遍了。

Java代码

class Solution {    public int numJewelsInStones(String J, String S) {        int result=0;        Map
    
      JMap = new HashMap<>();        for(Character c:J.toCharArray()){            JMap.put(c, 0);        }        for(Character c:S.toCharArray()){            Integer count = JMap.get(c);            if(count!=null){                result++;            }        }        return result;    }}