5 lines of Java (beats >90%) + follow up


  • 3
    public boolean isSubsequence(String s, String t) {
        int lastIndex = -1;
        for (char c : s.toCharArray())
            if ((lastIndex = t.indexOf(c, lastIndex + 1)) < 0) 
                return false;
        return true;
    }
    

    If the second param woud be constant, we could precompute a lookup for it:

    Map<Character, TreeSet<Integer>> indices = new HashMap<>();
    public void precompute(String t) {
        indices.clear();
        for (int i = 0; i < t.length(); i++)
            indices.computeIfAbsent(t.charAt(i), k -> new TreeSet<>()).add(i);
    }
    public boolean isSubsequence(String s) {
        int lastIndex = -1;
        for (char c : s.toCharArray()) {
            TreeSet<Integer> currentIndices = indices.get(c);
            if (currentIndices == null) return false;
            Integer next = currentIndices.higher(lastIndex);
            if (next == null) return false;
            lastIndex = next;
        }    
        return true;
    }
    

Log in to reply
 

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