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

第一次提交代码

class Solution {

public:

    int numJewelsInStones(string J, string S) {

        int li=J.length();

        int lj=S.length();

        int count=0;

        for(int i=0;i<li;i++)

        {

                for(int j=0;j<lj;j++)

                {

                        if(S[j]==J[i])

                            count++;

                }

        }

        return count;

    }

}

时间复杂度O(MN)

LeetCode上最优解

int numJewelsInStones(stringJ,stringS){

    int res =0;

    set <char> setJ(J.begin(), J.end());

    for(chars : S)

        if(setJ.count(s)) 

            res++;

    return res; 

 }

此方法可以做到O(N)

此方法使用到了set方法，若要使用，需引入#include<set>

属于c++中的stl部分，不熟悉