10 line Java solution 13ms


  • 2
    A

    Iterate through S from left to right; check against chars on T from right to left.
    counts[i] stores occurrences of char t so far.

    public int numDistinct(String S, String T) {
        int[] counts = new int[T.length()];
        for (int indexS = 0; indexS < S.length(); indexS++) {
            for (int indexT = T.length() - 1; indexT >= 0; indexT--)
                if (T.charAt(indexT) == S.charAt(indexS)) 
                    counts[indexT] = indexT == 0 ? counts[indexT]+1 : counts[indexT]+counts[indexT-1];
        }
        return counts[counts.length-1];
    }

Log in to reply
 

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