Java array solution


  • 0
    public class Solution {
        public boolean canConstruct(String ransomNote, String magazine) {
            if (ransomNote==null || ransomNote.length() == 0) return true;
            if (magazine==null || magazine.length() == 0) return false;
            int[] counts = new int[256];
            for (char c: magazine.toCharArray()) {
                counts[c]++;
            }
            for (char c: ransomNote.toCharArray()) {
                if (counts[c]==0) return false;
                counts[c]--;
            }
            return true;
        }
    }
    

  • 0

    @yubad2000

    There is no need to spend an extra O(n) time to convert the strings to char array when you can access in constant time with charAt(). Your solution would take twice the time of a charAt() implementation, because it traverses both strings twice.


  • 0

    @DeusVult
    I understood what your concern was. However, using toCharArray to iterate a String object is faster than using charAt(). My solution using toCharArray is about 12 ms while using charAt() is about 20ms. You can test this yourself.
    Here is the implementation of charAt() function:

    public char charAt(int index) {
        if ((index < 0) || (index >= value.length)) {
            throw new StringIndexOutOfBoundsException(index);
        }
        return value[index];
    }
    

    The reason why it is slower might be that charAt() needs to check whether the index is in the range.


  • 0

    Use counts[c-'a'] rather than counts[c] can save some space. That can shrink the size of counts from 256 to 26.


  • 0

    @yubad2000

    I have tested this myself as well, and confirm your conclusions. ~12 ms for toCharArray() and ~18 ms for charAt().

    This is very interesting to hear, and goes against intuition.

    However, I think this may simply be bias for the test cases provided by OJ. Given a significantly long string, I think toCharArray should be slower.

    In this stackoverflow resource: http://stackoverflow.com/questions/196830/what-is-the-easiest-best-most-correct-way-to-iterate-through-the-characters-of-a

    A user tested results using a very long string (1 million characters). He found that charAt() is more than twice as fast as toCharArray().


  • 0

    @Nakanu I agree. However, the tradeoff is spending more time on the operation of c-'a'.


Log in to reply
 

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