Concise JAVA solution based on DP


  • 8

    Explanation

    At first, I tried memorized DFS solution, but got stack overflow with the last large case. So then I was thinking about the non-recursive solution with DP, which is actually a bottom up memorized DFS solution without using stack.

    DP Solution:

    public static int numDistinct(String s, String t) {
    	int dp[][] = new int[s.length()+1][t.length()+1]; //dp[i][j]: number of the sequences for i long s and j long t
    	for (int i = 0; i < s.length(); i++)
    		dp[i][0] = 1;
    	
    	for (int i = 1; i <= s.length(); i++) {
    		for (int j = 1; j <= t.length(); j++) {
    			if (s.charAt(i-1) == t.charAt(j-1))// index = length - 1
    				//dp[i-1][j]  : don't take s[i-2]
    				//dp[i-1][j-1]: take s[i-2] 
    				dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
    			else 
    				dp[i][j] = dp[i-1][j];
    		}
    	}		
    	return dp[s.length()][t.length()];
    }
    

    DFS Solution: (Stack Overflow)

     int slen, tlen;
     int nums[][];
     public int numDistinct(String s, String t) {
    	 slen = s.length(); tlen = t.length();
    	 nums = new int[slen][tlen];
    	 for (int i = 0; i < slen; i++)
    		 Arrays.fill(nums[i], -1);
    	 return DFS(0, 0, s.toCharArray(), t.toCharArray(), 0, 0);		
     }
    
     int DFS(int curLen, int si, char[] s, char[] t, int ti, int count) {
    	 if (si > slen - 1 || ti > tlen - 1 || curLen == tlen) {
    		 if (curLen == tlen) 
    			 count++;			 
    		 return count;
    	 } 
    	 if (nums[si][ti] != -1) return nums[si][ti];			 
    	 if (s[si] == t[ti]) count += DFS(curLen + 1, si + 1, s, t, ti + 1, 0);// Take si char
    	 count += DFS(curLen, si + 1, s, t, ti, 0);// Don't take si char			 
    	 nums[si][ti] = count;
    	 return count;
     }

Log in to reply
 

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