771. Jewels and Stones

柔光的暖阳◎ 2022-05-31 09:49 183阅读 0赞

Description:

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

Example1:

Input: J = “aA”, S = “aAAbbbb”
Output: 3

Example2:

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.

Solution:

问题解析:
对于代表石头的字符串S中,每个字母看做一种宝石,那么这个问题就是计算出字符串J中的每个字符在字符串中出现的次数和,其中区分大小写。
思路一:
最笨的思路,遍历字符串S和字符串J,如果字符相同则计数加1
时间复杂度O(J.length*S.length)
空间复杂度O(1)

  1. int sum = 0;
  2. for(char j : J.toCharArray())
  3. {
  4. for(char s : S.toCharArray())
  5. {
  6. if(s == j){
  7. sum ++;
  8. }
  9. }
  10. }

思路二:
利用HashSet这个结构,将宝石作为HashSet的键值key,再遍历字符串S,HashSet中是否已存在这些key值
时间复杂度O(J.length + S.length)
空间复杂度:O(J.length)

  1. class Solution {
  2. public int numJewelsInStones(String J, String S) {
  3. int sum = 0;
  4. Set jewel = new HashSet();
  5. for(char c : J.toCharArray()){
  6. jewel.add(c);
  7. }
  8. for(char c : S.toCharArray()){
  9. if(jewel.contains(c)){
  10. sum ++;
  11. }
  12. }
  13. return sum;
  14. }
  15. }

发表评论

表情:
评论列表 (有 0 条评论,183人围观)

还没有评论,来说两句吧...

相关阅读