ఆభరణాలు మరియు రాళ్ళు లీట్‌కోడ్ పరిష్కారం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది Adobe అమెజాన్ ఆపిల్ <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గూగుల్ మైక్రోసాఫ్ట్ యాహూ
హాష్ మ్యాప్

సమస్య ఆభరణాలు మరియు స్టోన్స్ లీట్‌కోడ్ సొల్యూషన్ మీకు రెండు తీగలను ఇచ్చిందని పేర్కొంది. వాటిలో ఒకటి ఆభరణాలను సూచిస్తుంది మరియు వాటిలో ఒకటి రాళ్లను సూచిస్తుంది. ఆభరణాలను కలిగి ఉన్న స్ట్రింగ్ ఆభరణాల అక్షరాలను సూచిస్తుంది. రాళ్ల స్ట్రింగ్‌లోని ఆభరణాల సంఖ్యల సంఖ్యను మనం కనుగొనాలి. కాబట్టి, కొన్ని ఉదాహరణలను పరిశీలిద్దాం.

ఆభరణాలు మరియు రాళ్ళు లీట్‌కోడ్ పరిష్కారం

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

వివరణ: రాళ్ల స్ట్రింగ్ నుండి మనం చూడగలిగినట్లుగా, 'A' యొక్క రెండు ఉదాహరణలు మరియు 'a' యొక్క ఒక ఉదాహరణ ఉన్నాయి. ఆ విధంగా రాళ్ల స్ట్రింగ్‌లో మొత్తం 3 ఆభరణాలు ఉన్నాయి. అందువల్ల సమాధానం.

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

వివరణ: ఆభరణాల స్ట్రింగ్‌లో ఒకే చిన్న 'z' ఉన్నందున. మరియు రాళ్ల స్ట్రింగ్‌లో రెండు పెద్ద 'Z' ఉన్నాయి. తనిఖీ కేస్ సెన్సిటివ్ కాబట్టి. రాళ్ల తీగలో ఆభరణాలు లేవు.

ఆభరణాలు మరియు స్టోన్స్ లీట్‌కోడ్ సొల్యూషన్ కోసం బ్రూట్ ఫోర్స్ అప్రోచ్

సమస్య ఆభరణాలు మరియు స్టోన్స్ లీట్‌కోడ్ సొల్యూషన్ రాళ్ల స్ట్రింగ్‌లోని ఆభరణాల సంఖ్యను కనుగొనమని అడుగుతుంది. ఆభరణాల సంఖ్యను కనుగొనడానికి మేము సరళ శోధన చేయవచ్చు. రాళ్ల స్ట్రింగ్ యొక్క ప్రస్తుత అక్షరం ఒక ఆభరణమా అని తనిఖీ చేసే ఉచ్చుల కోసం మేము రెండు సమూహాలను ఉపయోగిస్తాము. ప్రస్తుత పాత్ర ఒక ఆభరణమని తేలితే, మేము మా జవాబును పెంచుతాము. ఇది రెండు సమూహ ఉచ్చులను ఉపయోగిస్తున్నందున విధానం నెమ్మదిగా ఉంటుంది.

ఆభరణాలు మరియు స్టోన్స్ లీట్‌కోడ్ సొల్యూషన్ కోసం బ్రూట్ ఫోర్స్ కోడ్

సి ++ కోడ్

#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

జావా కోడ్

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 అనేది రాళ్ల స్ట్రింగ్ యొక్క పొడవు. అందువలన సమయం సంక్లిష్టత బహుపది.

అంతరిక్ష సంక్లిష్టత

ఓ (1), మేము ఏ శ్రేణి లేదా వెక్టర్ ఉపయోగించము కాబట్టి. మేము స్థిరమైన స్థలాన్ని మాత్రమే ఉపయోగిస్తున్నాము. అందువలన బ్రూట్ విధానం స్థిరమైన స్థల సంక్లిష్టతను కలిగి ఉంటుంది.

ఆభరణాలు మరియు స్టోన్స్ లీట్‌కోడ్ సొల్యూషన్ కోసం ఆప్టిమైజ్డ్ అప్రోచ్

బ్రూట్ ఫోర్స్ విధానం నెమ్మదిగా ఉంటుంది కాబట్టి. మేము హాష్సెట్ ఉపయోగించి పై విధానాన్ని ఆప్టిమైజ్ చేయడానికి ప్రయత్నిస్తాము. ఆభరణాల స్ట్రింగ్ నుండి అక్షరాలను నిల్వ చేయడానికి మేము హాష్‌సెట్‌ను ఉపయోగిస్తాము. రాళ్ల స్ట్రింగ్ నుండి ప్రస్తుత అక్షరం ఒక ఆభరణమా అని తనిఖీ చేయడానికి మేము ఉపయోగించిన ఫర్ లూప్, ఇప్పుడు O (1) సమయంలో తనిఖీ చేయవచ్చు. ఈ ఆప్టిమైజేషన్ హాష్‌సెట్‌ను ఉపయోగించడం వల్ల. ప్రస్తుత అక్షరం హాష్‌సెట్‌లో ఉందో లేదో ఇప్పుడు మనం తనిఖీ చేయవచ్చు. అది ఉంటే హాష్‌సెట్, మేము మా జవాబును పెంచుతాము.

కోడ్

సి ++ కోడ్

#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

జావా కోడ్

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 ఆభరణాలు మరియు రాళ్ల స్ట్రింగ్ యొక్క పరిమాణం. మేము హాష్‌సెట్‌లను ఉపయోగించినందున ఆప్టిమైజేషన్ సాధించబడుతుంది. ఇప్పుడు, సమయ సంక్లిష్టత సరళంగా తగ్గించబడింది.

అంతరిక్ష సంక్లిష్టత

పై), మేము ఆభరణాల స్ట్రింగ్ నుండి అక్షరాలను నిల్వ చేస్తున్నందున. స్థల సంక్లిష్టత ఆభరణాల స్ట్రింగ్ పరిమాణంపై ఆధారపడి ఉంటుంది.