宝石和宝石Leetcode解决方案


难度级别 易得奖学金
经常问 土砖 亚马逊 Apple Facebook 谷歌 微软 雅虎
哈希图

Jewels and Stones Leetcode Solution问题指出您有两个字符串。 其中之一代表珠宝,其中之一代表宝石。 包含珠宝的字符串表示作为珠宝的字符。 我们需要在宝石字符串中找到作为珠宝的字符数。 因此,让我们看一些示例。

宝石和宝石Leetcode解决方案

jewels = "aA", stones = "aAAbbbb"
3

说明:从石头串中可以看到,有两个实例“ A”和一个实例“ a”。 因此,石头绳子中总共有3个珠宝。 因此答案。

jewels = "z", stones = "ZZ"
0

说明:由于珠宝串中只有一个小写字母“ z”。 石头弦中有两个大写的“ Z”。 由于检查是区分大小写的。 石头串中没有珠宝。

珠宝和宝石Leetcode解决方案的暴力破解方法

宝石和宝石Leetcode解决方案的问题要求我们找出宝石串中宝石的数量。 我们可以进行线性搜索以找到珠宝的数量。 我们将使用两个嵌套的for循环,检查石头串的当前字符是否是珠宝。 然后,如果发现当前角色是珠宝,我们增加答案。 但是这种方法很慢,因为它使用了两个嵌套循环。

珠宝和宝石Leetcode解决方案的蛮力代码

C ++代码

#include<bits/stdc++.h>
using namespace std;

int numJewelsInStones(string jewels, string stones) {
    int answer = 0;
    for(int i=0; i<stones.length();i++){
        for(int j=0;j<jewels.length();j++){
            if(stones[i] == jewels[j])
                answer++;
        }
    }
    return answer;
}

int main(){
    string jewels = "aA", stones = "aAAbbbb";
    cout<<numJewelsInStones(jewels, stones);
}
3

Java代码

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int numJewelsInStones(String jewels, String stones) {
        int answer = 0;
        for(int i=0; i<stones.length();i++){
            for(int j=0;j<jewels.length();j++){
                if(stones.charAt(i) == jewels.charAt(j))
                    answer++;
            }
        }
        return answer;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    String jewels = "aA";
    String stones = "aAAbbbb";
    System.out.println(numJewelsInStones(jewels, stones));
  }
}
3

复杂度分析

时间复杂度

O(N * M),其中N是珠宝串的长度,而M是宝石串的长度。 因此,时间复杂度是多项式。

空间复杂度

O(1), 因为我们不使用任何数组或向量。 我们仅使用恒定的空间。 因此,粗暴的方法具有恒定的空间复杂性。

珠宝和宝石Leetcode解决方案的优化方法

由于暴力破解方法很慢。 我们尝试使用HashSet优化上述方法。 我们使用一个HashSet来存储来自珠宝字符串的字符。 现在可以在O(1)时间中检查用于检查宝石字符串中当前字符是否为珠宝的for循环。 该优化是因为使用了HashSet。 现在,我们可以简单地检查HashSet中是否存在当前字符。 如果在 哈希集,我们增加答案。

代码

C ++代码

#include<bits/stdc++.h>
using namespace std;

int numJewelsInStones(string jewels, string stones) {
    unordered_set<char> jewelSet;
    for(int i=0;i<jewels.length();i++)
        jewelSet.insert(jewels[i]);

    int answer = 0;
    for(int i=0;i<stones.length();i++){
        if(jewelSet.count(stones[i]) == true)
            answer++;
    }
    return answer;
}

int main(){
    string jewels = "aA", stones = "aAAbbbb";
    cout<<numJewelsInStones(jewels, stones);
}
3

Java代码

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> jewelSet = new HashSet<Character>();
        for(int i=0;i<jewels.length();i++)
            jewelSet.add(jewels.charAt(i));
        
        int answer = 0;
        for(int i=0;i<stones.length();i++){
            if(jewelSet.contains(stones.charAt(i)) == true)
                answer++;
        }
        return answer;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    String jewels = "aA";
    String stones = "aAAbbbb";
    System.out.println(numJewelsInStones(jewels, stones));
  }
}
3

复杂度分析

时间复杂度

O(N + M), 其中N和M是珠宝和宝石串的大小。 因为我们利用了HashSets,所以实现了优化。 现在,时间复杂度已降低至线性。

空间复杂度

上), 因为我们存储了珠宝字符串中的字符。 空间的复杂性取决于珠宝首饰的琴弦大小。