Why is indexOf in Java faster than charAt?


  • 0

    So the solution to this is pretty straightforward.

    This is the charAt solution (25+ ms):

    public class Solution {
        public boolean isSubsequence(String s, String t) {
            if(s == null || t == null) {
                return false;
            }
            else if(s.length() == 0) {
                return true;
            }
            int pointer = 0;
            char c = s.charAt(0);
            for(int x = 0; x < t.length(); x++) {
                if(c == t.charAt(x)) {
                    if(++pointer >= s.length()) {
                        return true;
                    }
                    c = s.charAt(pointer);
                }
            }
            return false;
        }
    }
    

    And this is the indexOf solution (2 ms):

    public class Solution {
       public boolean isSubsequence(String s, String t) {
            if(s == null || t == null || t.length() < s.length()) {
                return false;
            }
            int pointer = 0;
            for(int x = 0; x < s.length(); x++) {
                pointer = t.indexOf(s.charAt(x), pointer);
                if(pointer++ == -1) {
                    return false;
                }
            }
            return true;
        }
    }
    

    Fairly straightforward, but why is the indexOf() solution an order of magnitude better than charAt? It would make sense if a toCharArray() solution that converted the entire string "t" into an array took that long. But how exactly does charAt(), which should have constant time access to each element of the array, end up ten times slower than indexOf(), which, in best case, does the exact same thing?

    Can anyone shed some light on this?


  • 0
    W

    @DeusVult

    I guess the reason is the code below in charAt() method.

    if ((index < 0) || (index >= value.length)) {
        throw new StringIndexOutOfBoundsException(index);
    }
    

    Moreover Using charAt,there are many variable assignments.

    However I was really shocked by the difference


Log in to reply
 

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