જ્વેલ્સ અને સ્ટોન્સ લીટકોડ સોલ્યુશન


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન સફરજન ફેસબુક Google માઈક્રોસોફ્ટ યાહૂ
હેશમેપ

જ્વેલ્સ અને સ્ટોન્સ લીટકોડ સોલ્યુશનમાં સમસ્યા જણાવે છે કે તમને બે તાર આપવામાં આવે છે. તેમાંથી એક ઝવેરાતનું પ્રતિનિધિત્વ કરે છે અને તેમાંથી એક પત્થરોનું પ્રતિનિધિત્વ કરે છે. ઝવેરાત ધરાવતો શબ્દમાળા ઝવેરાતનાં અક્ષરો રજૂ કરે છે. આપણે પત્થરોના શબ્દમાળા અક્ષરોની સંખ્યા શોધવાની જરૂર છે જે ઝવેરાત છે. તેથી, ચાલો થોડા ઉદાહરણો જોઈએ.

જ્વેલ્સ અને સ્ટોન્સ લીટકોડ સોલ્યુશન

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

સમજૂતી: જેમ આપણે પત્થરોની તારથી જોઈ શકીએ છીએ, ત્યાં 'એ' ના બે દાખલા છે, અને 'એ' ના દાખલા. આમ પત્થરોના તારમાં કુલ 3 ઝવેરાત છે. તેથી જવાબ.

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

સમજૂતી: ઝવેરાતના તારમાં એક જ લોઅરકેસ '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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન * એમ), જ્યાં એન ઝવેરાતની તારની લંબાઈ છે અને એમ પત્થરોની તારની લંબાઈ છે. આમ સમય જટિલતા બહુપદી છે.

અવકાશ જટિલતા

ઓ (1), કારણ કે આપણે કોઈપણ એરે અથવા વેક્ટરનો ઉપયોગ કરતા નથી. અમે ફક્ત સતત જગ્યા વાપરી રહ્યા છીએ. આમ જડ અભિગમમાં સતત જગ્યાની જટિલતા હોય છે.

જ્વેલ્સ અને સ્ટોન્સ લીટકોડ સોલ્યુશન માટે timપ્ટિમાઇઝ અભિગમ

કારણ કે જડ બળ અભિગમ ધીમું છે. અમે હેશસેટનો ઉપયોગ કરીને ઉપરોક્ત અભિગમને optimપ્ટિમાઇઝ કરવાનો પ્રયાસ કરીએ છીએ. ઝવેરાતની તારમાંથી અક્ષરો સંગ્રહવા માટે અમે હેશસેટનો ઉપયોગ કરીએ છીએ. આપણે જે પત્થરોના તારમાંથી વર્તમાન પાત્ર રત્ન છે તે તપાસવા માટે લૂપનો ઉપયોગ હવે ઓ (1) સમયમાં કરી શકાય છે. આ optimપ્ટિમાઇઝેશન હેશસેટનો ઉપયોગ કરવાને કારણે છે. હવે આપણે ખાલી તપાસ કરી શકીએ કે વર્તમાન અક્ષર હેશસેટમાં હાજર છે કે નહીં. જો તે છે હેશસેટ, અમે અમારા જવાબ વધારો.

કોડ

સી ++ કોડ

#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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન + એમ), જ્યાં એન અને એમ ઝવેરાત અને પત્થરોના તારનું કદ છે. ઓપ્ટિમાઇઝેશન પ્રાપ્ત થયું છે કારણ કે અમે હેશસેટ્સનો ઉપયોગ કર્યો છે. હવે, સમય જટિલતા ઘટાડીને રેખીય કરવામાં આવી છે.

અવકાશ જટિલતા

ઓ (એન), કારણ કે આપણે ઝવેરાતનાં તારમાંથી અક્ષરો સંગ્રહિત કરીએ છીએ. અવકાશ જટિલતા ઝવેરાતનાં તારનાં કદ પર આધારિત છે.