Jewels And Stones


  • 0

    Click here to see the full article post


  • 0
    H

    Sorting of 2 strings(Say based on ASCII character, so all small letters would appear in the front followed by block letters as per ASCII code.
    Then compare each character in J with each character in S. Keep track of the previously visited place in each string visited.
    Then when once you reach end of string in one of the string, stop the while loop.

    Total time complexity,
    O(SlogS)--> sort the stone input, O(JlogJ)-->sort jewel input.'
    Max(O(J), O(S)) to check the matching.
    time complexity is O(SLogS) totally


  • 0
    Y

    Better solution here: https://discuss.leetcode.com/topic/118697/java-o-s-time-and-o-j-space/2

    public int numJewelsInStones(String J, String S) {
        boolean[] dictionary = new boolean[256];
        for(int i=0; i<J.length(); i++){
            dictionary[J.charAt(i)] = true;
        }
        int count = 0;
        for(int i=0; i<S.length(); i++){
            if(dictionary[S.charAt(i)]){
                count++;
            }
        }
        return count;
    }

  • 1
    V

    One line solution in Javascript

    var numJewelsInStones = function(J, S) {
        return S.split("").reduce((count, ele) => J.includes(ele) ? count + 1 : count, 0);
    };
    

  • 0
    O

    /C Implementation /
    int numJewelsInStones(char
    J, char
    S) {

    int nu_of_jewels = 0;
    char *jP = J;
    char *SP = S;

    while(*jP != '\0'){
    
            while(*SP != '\0'){
    
                if(*jP == *SP){
    
                    ++nu_of_jewels;
    
                }
                ++SP;
            }
    ++jP;
    SP = S;
    }
    

    return nu_of_jewels;

    }


  • 0
    O
    /*C Implementation */ 
    
    int numJewelsInStones(char* J, char* S) {
        
    int nu_of_jewels = 0;
    char *jP = J;
    char *SP = S;
    
        while(*jP != '\0'){
    
                while(*SP != '\0'){
    
                    if(*jP == *SP){
    
                        ++nu_of_jewels;
    
                    }
                    ++SP;
                }
        ++jP;
        SP = S;
        }
    
    return nu_of_jewels;
        
    }
    
    

  • 0
    A

    Space complexity for the brute force will be O(J.length+S.length)) not O(J.length∗S.length))


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.