ज्वेल्स र स्टोन्स लेटकोड समाधान


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब अमेजन एप्पल फेसबुक गुगल माइक्रोसफ्ट याहू
हशम्याप

समस्या ज्वेल्स र स्टोन्स लेटकोड समाधान बताउँछ कि तपाईंलाई दुईवटा तारहरू दिइयो। ती मध्ये एक रत्न प्रतिनिधित्व गर्दछ र ती मध्ये एक पत्थर प्रतिनिधित्व गर्दछ। स्ट्रि thatमा जेवेल्स समावेश हुन्छ जसले रत्नहरू हुन् भनेर पात्रहरूलाई प्रतिनिधित्व गर्दछ। हामीले पत्थरका अक्षरहरूमा अक्षरहरूको संख्या खोज्नु पर्छ जुन गहनाहरू हुन्। त्यसो भए, हामी केही उदाहरणहरूमा एक नजर राख्दछौं।

ज्वेल्स र स्टोन्स लेटकोड समाधान

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

स्पष्टीकरण: हामी ढु stones्गाको तारबाट देख्न सक्छौं, त्यहाँ दुईवटा उदाहरणहरू छन् 'A', र 'उदाहरण' को एक उदाहरण। यसैले ढु the्गाको स्ट्रि inमा जम्मा je गहनाहरू छन्। त्यसैले उत्तर।

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

स्पष्टीकरण: त्यहाँ रत्न स्ट्रि inमा एकल लोअरकेस 'z' छ। र त्यहाँ दुईवटा ठूला अक्षरहरू छन्। किनकी जाँच केस संवेदनशील छ। ढु the्गाको तारमा कुनै रत्नहरू छैनन्।

ज्वेल्स र स्टोन्स लीटकोड समाधानको लागि ब्रूट फोर्स अप्रोच

समस्या गहना र स्टोन्स लेटकोड समाधानले हामीलाई ढु stones्गाको तारमा गहनाको संख्या पत्ता लगाउन आग्रह गर्दछ। हामी जवाहरातको संख्या पत्ता लगाउन रैखिक खोजी गर्न सक्छौं। हामी लूपहरूको लागि दुई नेस्टेड प्रयोग गर्दछौं कि यदि ढु stones्गाको तारको वर्तमान चरित्र गहना हो कि होइन भनेर जाँच गर्दछौं। त्यसो भए यदि हालको चरित्र रत्न हो भने, हामी हाम्रो उत्तर वृद्धि गर्छौं। तर दृष्टिकोण ढिलो छ किनकि यसले दुई नेस्टेड लूपहरू प्रयोग गर्दछ।

ज्वेल्स र स्टोन्स लेटकोड समाधानको लागि ब्रुट फोर्स कोड

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

जावा कोड

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)जहाँ एन गहनाको ताराको लम्बाई हो र M ढु stones्गाको तारको लम्बाई हो। यसैले समय जटिलता बहुपद हो।

ठाउँ जटिलता

O (१), किनकि हामी कुनै एर्रे वा भेक्टर प्रयोग गर्दैनौं। हामी केवल स्थिर स्थान प्रयोग गर्दैछौं। यसैले ब्रुट दृष्टिकोणमा स्थिर स्थान जटिलता हुन्छ।

ज्वेल्स र स्टोन्स लेटकोड समाधानको लागि अनुकूलित दृष्टिकोण

क्रूर बल दृष्टिकोण ढिलो छ। हामी ह्याससेट प्रयोग गरेर माथिको दृष्टिकोण अप्टिमेट गर्न प्रयास गर्दछौं। हामी गहना स्ट्रिंगबाट अक्षरहरू भण्डारण गर्न ह्याससेट प्रयोग गर्दछौं। लूपको लागि जुन हामीले जाँच गर्न प्रयोग गर्थ्यौं यदि ढु stones्गाको स्ट्रिंगबाट हालको चरित्र गहना हो कि भनेर, अब हे (१) समयमा जाँच गर्न सकिन्छ। यो अप्टिमाइजेसन ह्याशसेटको प्रयोगको कारण हो। अब हामी केवल जाँच गर्न सक्छौं कि हालको चरित्र ह्याशसेटमा उपस्थित छ कि छैन। यदि यो छ भने ह्याससेट, हामी हाम्रो उत्तर वृद्धि।

कोड

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

जावा कोड

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), जहाँ एन र एम रत्न र पत्थर स्ट्रिंग को आकार छ। अप्टिमाइजेसन प्राप्त भयो किनकि हामीले ह्याशसेटको प्रयोग गर्‍यौं। अब, समय जटिलता लाईन लाई कम गरिएको छ।

ठाउँ जटिलता

O (N), किनकि हामी रत्न स्ट्रिंगबाट क्यारेक्टरहरू भण्डार गर्दछौं। अन्तरिक्ष जटिलता गहनाको स्ट्रिंग आकारमा निर्भर हुन्छ।