java with O(t.length)


  • 0
    E
    public boolean isSubsequence(String s, String t) {
            // sanity check
            if (s == null || t == null) {
                return false;
            }
            int s1 = s.length();
            int t1 = t.length();
            if (s1 == 0 && t1 != 0 || (s1 == 0 && t1 == 0)) {
                return true;
            } else if (s1 == 0 || t1 == 0) {
                return false;
            }
            // helper[i] represents the i-th char in s we are looking for
            int[] helper = new int[t1];
            if (s.charAt(0) == t.charAt(0)) {
                helper[0] = 1;
            }
            for (int i = 1; i < t1; i++) {
                if (s.charAt(helper[i - 1]) == t.charAt(i)) {
                    helper[i] = helper[i - 1] + 1;
                    if (helper[i] == s1) {
                        helper[t1 - 1] = s1;
                        break;
                    }
                } else {
                    helper[i] = helper[i - 1];
                }
            }
            return helper[t1 - 1] == s1 ? true : false;
        }
    

Log in to reply
 

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