Leetcode Distinct Subsequences
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.
Java solution
Here are three solutions to solve this problem.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
public class Solution { public int numDistinct(String s, String t) { int[][] cnt = new int[s.length() + 1][t.length() + 1]; //cnt[i][j] = cnt[i - 1][j] if s[i - 1] != t[j - 1]; //cnt[i][j] = cnt[i - 1][j] + cnt[i - 1][j - 1] if s[i - 1] == t[j - 1]; for(int i = 0; i< s.length(); i++) { cnt[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)) { cnt[i][j] = cnt[i - 1][j] + cnt[i - 1][j - 1]; } else { cnt[i][j] = cnt[i - 1][j]; } } } return cnt[s.length()][t.length()]; // return count(s.toCharArray(), s.length() - 1, t.toCharArray(), t.length() - 1); } // we can use only one array to have O(n) space complexity int dp(String s, String t){ if(s.length() < t.length()) return 0; int[] res = new int[s.length() + 1]; res[0] = 1; for(int i = 1; i <= s.length(); i++) { for(int j = t.length(); j > 0; j--) { if(s.charAt(i - 1) == t.charAt(j - 1) ) { res[j] += res[j - 1]; } } } return res[t.length()]; } // use recursion method, it doesn't work for long strings int count(char[] s, int sEnd, char[] t, int tEnd) { if(tEnd < 0 && sEnd >=0) return 1; if(sEnd < 0) return 0; if(tEnd == 0 && sEnd == 0 ) { if(s[sEnd] == t[tEnd]) return 1; else return 0; } int cnt = 0; if(s[sEnd] == t[tEnd]) { cnt = count(s, sEnd - 1, t, tEnd) + count(s, sEnd - 1, t, tEnd - 1); } else { cnt = count(s, sEnd - 1, t, tEnd); } return cnt; } } |
