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

给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。

示例 1:

输入: J = "aA", S = "aAAbbbb"
输出: 3

示例 2:

输入: J = "z", S = "ZZ"
输出: 0

注意:
S 和 J 最多含有50个字母。
J 中的字符不重复。

题解

1.思路：直接两层循环，外层遍历S，内层遍历J，相等直接内层break出去

 public int NumJewelsInStones(string J, string S)
        {
            int jewelCount = 0;
            for(int i = 0; i < S.Length; i++)
            {
                for(int j = 0; j < J.Length; j++)
                {
                    if(J[j] == S[i])
                    {
                        jewelCount++;
                        break;
                    }
                }
            }
            return jewelCount;
        }

时间复杂度n*n
空间复杂度0
2.将J存入List，遍历S，看J的List中是否有

            List<char> list = new List<char>();
            for(int i=0;i<J.Length; i++)
            {
                list.Add(J[i]);
            }
            for(int n = 0; n < S.Length; n++)
            {
                if (J.Contains(S[n]))
                {
                    jewelCount++;
                }
            }

时间复杂度n
空间复杂度n
3.Dictionary的Key存每一个S的char，value存char出现的次数。之后按J作为Key在dic中查找，找到将value加在jewelCount上。

 Dictionary<char, int> dic = new Dictionary<char, int>();
            for(int i=0;i<S.Length; i++)
            {
                int temp;
                if(dic.TryGetValue(S[i],out temp))
                {
                    dic[S[i]]++;
                }
                else
                {
                    dic.Add(S[i], 1);
                }
            }
            for(int n = 0; n < J.Length; n++)
            {
                int temp;
                if(dic.TryGetValue(J[n],out temp))
                {
                    jewelCount += temp;
                }
            }

时间复杂度n
空间复杂度n