Share My Easy to Understand 5 lines of Java Code, 13ms beats 96%


  • 15

    The code is fast mainly because it uses the ASCII value of the char in the string as the index of an array, resulting in direct access and thus significantly increases efficiency of the algorithm.

    public boolean canConstruct(String ransomNote, String magazine) {
        int[] table = new int[128];
        for (char c : magazine.toCharArray())   table[c]++;
        for (char c : ransomNote.toCharArray())
            if (--table[c] < 0) return false;
        return true;
    }
    

    If you think the above code has created some unnecessary spaces, the following code may be what you are looking for

    public boolean canConstruct2(String ransomNote, String magazine) {
        int[] table = new int[26];
        for (char c : magazine.toCharArray())   table[c - 'a']++;
        for (char c : ransomNote.toCharArray())
            if (--table[c - 'a'] < 0) return false;
        return true;
    }
    

    Here's another solution using Hash Map. Same idea, just using different data structures. And this solution obviously is less efficient than previous two.

    public boolean canConstruct3(String ransomNote, String magazine) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : magazine.toCharArray()) {
            int count = map.containsKey(c) ? map.get(c) + 1 : 1;
            map.put(c, count);
        }
        for (char c : ransomNote.toCharArray()) {
            int newCount = map.containsKey(c) ? map.get(c) - 1 : -1;
            if (newCount == -1) return false;
            map.put(c, newCount);
        }
        return true;
    }
    
    

  • 0

    @jeremylinlin could you explain the forth line?
    if (--table[c] < 0) return false;
    Here, --table[], I don't know how it works


  • 1

    @taylorzhangyx

    This line
    if (--table[c] < 0) return false;

    is equivalent to this line
    if (newCount == -1) return false;
    or
    if (newCount < 0) return false;
    in the Hash Map implementation.

    c is the current index number (using the letter's ASCII value) of the array.

    So putting -- in front of table[c] basically decrements its value first, and evaluates the condition afterwards. And the values stored in the array stand for the count of the character.


  • 0
    T

    Why is HashMap less efficient ?


  • 0
    D

    @tanya Overhead of the objects involved. In order to use a HashMap in Java, native types (int, char, etc.) must be wrapped in corresponding classes (Integer, Character, etc.), then unwrapped when you want to access them. Object creation and the corresponding garbage collection adds time complexity. However, using HashMap still results in O(n) runtime.


  • 0
    Y
    This post is deleted!

  • 0

    I wrote exactly the same code in C++, but was beaten by 96%...


  • 0
    I

    @drewda81 I also think when you use a HashMap the space complexity is O(N) whereas if you an array, the space complexity remains O(1). Your thoughts?


  • 0
    D

    @ironman7 They should both be O(1). In either case you will have a max of 26 entries. Keep in mind that when the algorithm calls put(c, count) or put put(c, newCount), the previous value for c in the map is being overwritten with the new value.


  • 0
    I

    @drewda81 Yes, I do agree. But in case of an array the number of slots is fixed (128 here) and not dependent on the size of input, but in case of HashMap, the number of slots depends on size of input strings. Thats the reason why I said HashMap takes O(N) space.Please correct me if I am wrong.. :)


  • 0

    @ironman7 Hello, I am a little curious about the size of the array too, I mean, why you assign it to 128?


  • 1
    I

    @wxl163530 The size 128 represents the number of characters in ASCII set. Please take a look at the table in http://www.asciitable.com/


  • 0

    @ironman7 Thanks for sharing


  • 0
    J

    Thanks for sharing!


Log in to reply
 

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