Java 15ms O(m+n) greedy solution


  • 0

    Idea: Loop by characters in s since the size of s is much smaller. One pick a character with index i from s. Compare it with the character in t. Once s[i]==t[j], mark j as last. When u check s[i+1], t should be checked starting from last+1. Both of s and t will be traversed only once. So the time complexity is (O(m+n)).

    public boolean isSubsequence(String s, String t) {
        if(s.length()==0) return true;
        char[] cs = s.toCharArray();
        char[] ct = t.toCharArray();
        int last = -1;
        for(int i = 0;i<cs.length;i++){
            for(int j = last+1;j<ct.length;j++){
                if(cs[i]==ct[j]){
                    if(i==cs.length-1) return true;
                    last = j;
                    break;
                }
                if(j==ct.length-1) return false;
            }
        }
        return false;
    }

Log in to reply
 

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