Java DFS solution beats 99%

  • 0

    Unlike most most DP solutions, I have figured out a solution using DFS with a memo(or is this a top-down DP with memo? I am not sure..)
    This Java solution beats 99% of the acceptances.

    public static int numDistinct(String s, String t) {
            if(s.length()<t.length()) return 0;
            int rs = checkNext(t.toCharArray(),0,
                s.toCharArray(),0,new int[t.length()][s.length()]);
            return rs<0?0:rs;
    private static int checkNext(char[] t,int tarindex,char[] s,int begin,
                                     int[][] memo){
        // flags in the memo: 0 undecided, -1 not match(return directly)
        // other integers represent the numbers of subsequences.
        if(tarindex==t.length) return 1;
        if(memo[tarindex][begin]!=0) return memo[tarindex][begin];
        int count = 0,remain = t.length-tarindex;
        for(int i=begin;i<=s.length-remain;i++){
                int rs = checkNext(t,tarindex+1,s,i+1,memo);
                if(rs!=-1) count+=rs;
                else break; // no more subsequences, stop checking
        count = count==0?-1:count;
        memo[tarindex][begin] = count;
        return count;

Log in to reply

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