0

I have two answers to a question on leetcode.Is Subsequence

1

Runtime: 9 ms, faster than 42.67% of Java online submissions for Is Subsequence. Memory Usage: 42.5 MB, less than 100.00% of Java online submissions for Is Subsequence.

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i=0,j=0;
        while(i<s.length()&&j<t.length()){
            if(s.charAt(i)==t.charAt(j))
                ++i;
            ++j;
        }
        return i==s.length();
    }
}

2

Runtime: 1 ms, faster than 100.00% of Java online submissions for Is Subsequence. Memory Usage: 42.5 MB, less than 100.00% of Java online submissions for Is Subsequence.

class Solution {
    public boolean isSubsequence(String s, String t) {
        char[] arr = s.toCharArray();
        int index = -1;
        for(int i=0;i<s.length();++i){
            index = t.indexOf(arr[i],index+1);
            if(index<0)
                return false;
        }
        return true;
    }
}

I think indexOf() is essentially looking for index by traversing String.Inside this indexOf() still need to loop and traverse.

But why the second solution is more efficient than the first？

user12471964
  • 1
  • You probably need to look at https://stackoverflow.com/questions/33646781/java-performance-string-indexofchar-vs-string-indexofsingle-string – Satish Patel Apr 29 '20 at 04:25
  • have you used jvisualvm to profile the two versions? – Jeff Holt Apr 29 '20 at 04:25
  • Your current numbers may not be accurate, and you should review how to benchmark a Java application. – Tim Biegeleisen Apr 29 '20 at 04:26
  • 1
    You second variant returns immediately when a character has not been found. You first variant always loops over the entire string, potentially performing unnecessary comparisons. Note that the second variant still is doing unnecessary work by first copying the string into a `char[]` array though. – Holger Apr 29 '20 at 13:49

0 Answers0