Java. Only 2ms. Much faster than normal 2 pointers.


  • 19

    Actually another way of 2 pointers, guess indexOf() performs better.

    Tested with other 2-pointers methods in discussion, both took 30ms+.

    The one below only takes 2ms.

    public class Solution 
    {
        public boolean isSubsequence(String s, String t) 
        {
            if(t.length() < s.length()) return false;
            int prev = 0;
            for(int i = 0; i < s.length();i++)
            {
                char tempChar = s.charAt(i);
                prev = t.indexOf(tempChar,prev);
                if(prev == -1) return false;
                prev++;
            }
            
            return true;
        }
    }
    

    Thanks to @Ankai.Liang who looked into both functions and provided us the answer.

    In case you guys do not notice, I post Liang Ankai's answer.

    @Ankai.Liang said

    Hi, good solution.
    I checked the origin code of func "indexOf" and "charAt". These two solution both traversed the char of String one by one to search the first occurrence specific char.
    The difference is that indexOf only call once function then traversed in "String.value[]" arr, but we used multiple calling function "charAt" to get the value in "String.value[]" arr.
    The time expense of calling function made the difference.


  • 2
    W

    you can code like below, just 3 lines.

    public boolean isSubsequence(String s, String t) {
        for (int sIdx = 0, tIdx = -1; sIdx < s.length();)
            if ((tIdx = t.indexOf(s.charAt(sIdx++), ++tIdx)) == -1) return false;
        return true;
    }
    

    I think this is common sense that you can not make your code short and clear at the same time in most cases. Coding is a tradeoff between brevity and readablity. I think it is very obvious.

    I just share another way of coding. A very awsome answer sharer StefanPochmann often provides answers as short as possible, so they are not very easy to read.
    The reason of that somebody do not reply his answer "not readable", "readablity is more important"...blur blur is really beyond me. I guess is just immaturity.

    Now is chinese old saying time for this situation,"The questions you asked are too young, too simple, sometimes naive" "You need more learning" "Do you understand".


  • 6
    L

    @wit But your code does not that easy to read


  • 10
    L

    @wit readability is more important than code lines


  • 0

    @wit
    Thx for sharing.


  • 0
    I

    @reboot329 WHY indexOf is faster?

        public boolean isSubsequence(String s, String t) {
            if (s.length() > t.length()) return false;
            int prev = -1;
            for (char ch : s.toCharArray()) {
                prev = t.indexOf(ch, prev + 1);
                if (prev < 0) return false;
            }
            return true;
        }
    

  • 0

    @iambright
    Hi,

    To be honest, I have no idea.

    I did not expect this until I saw the result, and I was hoping someone explain why using indexOf() faster than manually using charAt().

    If someone answers, I will let you know.


  • 10
    A

    Hi, good solution.
    I checked the origin code of func "indexOf" and "charAt". These two solution both traversed the char of String one by one to search the first occurrence specific char.
    The difference is that indexOf only call once function then traversed in "String.value[]" arr, but we used multiple calling function "charAt" to get the value in "String.value[]" arr.
    The time expense of calling function made the difference.


  • 0

    @Ankai.Liang

    You nailed it!

    I will quote your answer on top and let others check it.

    Thank you to explain this.


  • 0

    @iambright
    Ankai,Liang has a good explanition. Check it out.


  • 0
    B

    @wit It's not readable


  • 0
    W

    @bwju

    I think this is common sense that you can not make your code short and clear at the same time in most cases. Coding is a tradeoff between brevity and readablity. I think it is very obvious.

    I just share another way of coding. A very awsome answer sharer StefanPochmann often provides answers as short as possible, so they are not very easy to read.
    The reason of that you do not reply his answer "not readable", "readablity is more important"...blur blur is really beyond me. I guess is just immaturity.

    Now is chinese old saying time for this situation,"The questions you asked are too young, too simple, sometimes naive" "You need more learning" "Do you understand".


  • 1

    Sorry but still cannot understand why indexOf() is faster which is counter-intuitive... Why charAt(i) traverse the char array? I insist the normal 2 pointer version is more understandable. Anyway, thanks for sharing~

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

  • 0
    U

    For interview, I think it is better to use 2 pointer version.


  • 0
    S
    This post is deleted!

  • 2
    S

    @Ankai.Liang

    If we just compare indexOf and charAt, indexOf(should be O(n), not sure) is much slower than charAt(O(1)).

    The reason why for this question indexOf is much faster is because it loops s.length times. Most charAt solution loops over all t.length.

    In the test case, t is much larger than s. As result, we could get 2ms for indexOf, and 30ms for charAt.


  • 0
    C

    Another suggestion, char[] sa = s.toCharArray(), using sa[i] is faster than s.charAt(i)


  • 0
    X

    @wit You are doing great. I vote you up. Your idea is basically the same with the top solution so I can't understand why they say your code unreadable. Just the same idea in different codes.
    +1s for you.


  • 0
    This post is deleted!

  • 0

    @codecola The toCharArray() solution takes 18ms, which is better than charAt() but still worse than indexOf()
    Here is my code for your reference.

    //18ms 84% - Another test of char array using toCharArray() function
    public class Solution {
        public boolean isSubsequence(String s, String t) {
            char[] sch=s.toCharArray(), tch=t.toCharArray();
            int i=-1, j=-1;
            while(++i<s.length()){
                while(++j<t.length() && tch[j]!=sch[i]) ;//i and j will point to the same char if any
                if(j==t.length()) return false;
            }
            return true;
        }
    }
    

Log in to reply
 

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