לעעטקאָדע לייזונג פֿאַר דזשעוועלס און שטיינער


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַדאָובי אַמאַזאָן עפּל facebook גוגל מייקראָסאָפֿט יאַהאָאָ
האַשמאַפּ

די פּראָבלעם דזשולז און סטאָנעס לעעטקאָדע סאַלושאַן זאגט אַז איר האָט צוויי סטרינגס. איינער פון זיי רעפּראַזענץ דזשולז און איינער פון זיי רעפּראַזענץ שטיינער. די שטריקל וואָס כּולל דזשולז רעפּראַזענץ די אותיות וואָס זענען דזשולז. מיר דאַרפֿן צו געפֿינען די נומער פון אותיות אין די שטיינער שטריקל וואָס זענען דזשולז. לאָמיר נעמען עטלעכע ביישפילן.

לעעטקאָדע לייזונג פֿאַר דזשעוועלס און שטיינער

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

דערקלערונג: ווי מיר קענען זען פון די שטיינער שטריקל, עס זענען צוויי ינסטאַנסיז פון 'א' און איין בייַשפּיל פון 'אַ'. אזוי עס זענען אַ גאַנץ פון 3 דזשולז אין די שטיינער שטריקל. דערפאר די ענטפער.

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

דערקלערונג: זינט עס איז אַ קליין "Z" אין די דזשולז שטריקל. און עס זענען צוויי גרויסע אותיות 'Z' אין די שטיינער שטריקל. זינט קאָנטראָלירונג איז פאַלש שפּירעוודיק. עס זענען קיין דזשולז אין די שטיינער שטריקל.

ברוט פאָרס אַפּפּראָאַטש פֿאַר דזשולז און סטאָנעס לעעטקאָדע סאַלושאַן

די פּראָבלעם דזשעוועלס און סטאָנעס לעעטקאָדע סאַלושאַן פרעגט אונדז צו געפֿינען די נומער פון דזשולז אין די שטיינער שטריקל. מיר קענען דורכפירן אַ לינעאַר זוכן צו געפֿינען די נומער פון דזשולז. מיר נוצן צוויי נעסטעד פֿאַר לופּס וואָס קאָנטראָלירן אויב די קראַנט כאַראַקטער פון די שטיינער שטריקל איז אַ בריליאַנט. אויב דער איצטיקער כאַראַקטער איז אַ בריליאַנט, מיר ינקרעמענט אונדזער ענטפער. אָבער דער צוגאַנג איז פּאַמעלעך ווייַל עס ניצט צוויי נעסטעד לופּס.

ברוט פאָרס קאָד פֿאַר דזשולז און סטאָנעס לעעטקאָדע סאַלושאַן

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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N * ב), ווו N איז די לענג פון די דזשולז שטריקל און M איז די לענג פון די שטיינער שטריקל. אזוי די צייט קאַמפּלעקסיטי איז פּאַלינאָומיאַל.

ספעיס קאַמפּלעקסיטי

אָ (1), זינט מיר טאָן ניט נוצן קיין מענגע אָדער וועקטאָר. מיר נוצן בלויז קעסיידערדיק פּלאַץ. אַזוי דער ברוט צוגאַנג האט קעסיידערדיק פּלאַץ קאַמפּלעקסיטי.

אָפּטימיזעד אַפּפּראָאַטש פֿאַר דזשולז און סטאָנעס לעעטקאָדע סאַלושאַן

זינט די ברוט קראַפט צוגאַנג איז פּאַמעלעך. מיר פּרובירן צו אַפּטאַמייז די אויבן צוגאַנג מיט HashSet. מיר נוצן אַ האַשסעט צו קראָם די אותיות פון די דזשולז שטריקל. דער פאָר שלייף וואָס מיר געוויינט צו קאָנטראָלירן אויב די קראַנט כאַראַקטער פון די שטיינער שטריקל איז אַ בריליאַנט, קענען איצט זיין אָפּגעשטעלט אין אָ (1) צייט. די אַפּטאַמאַזיישאַן איז ווייַל פון די 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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N + M), וווּ N און M איז די גרייס פון דזשולז און שטיינער שטריקל. דער אָפּטימיזאַטיאָן איז אַטשיווד ווייַל מיר האָבן כאַשייזד. די צייט קאַמפּלעקסיטי איז רידוסט צו לינעאַר.

ספעיס קאַמפּלעקסיטי

אָ (N), זינט מיר קראָם די אותיות פון די דזשולז שטריקל. די פּלאַץ קאַמפּלעקסיטי איז אָפענגיק אויף די שטריקל גרייס פון די דזשולז.