首页 > 代码库 > LeetCode OJ - Distinct Subsequence
LeetCode OJ - Distinct Subsequence
这道题采用动态规划,可是我一开始没有想到。后来参考了discuss中前辈的代码和思路,才想通的。 方法二是因为每一步只和上一步的内容相关,所以可以只用O(n)的空间复杂度。
下面是AC代码:
1 /** 2 * Solution DP 3 * we keep a m*n matrix and scanning through string T, 4 * p[i][j] means the number of distinct subsequence of S(0...j) equal to T(0...i) 5 * p[i][j] = p[i][j-1] discard s[j] 6 * + 0 if s[j] != t[i] 7 * + p[i-1][j-1] if s[j] == t[i] 8 * @param S 9 * @param T 10 * @return 11 */ 12 public int numDistinct1(String S, String T){ 13 if(S.length()<T.length()) 14 return 0; 15 int[][] p = new int[T.length()][S.length()]; 16 //for convenient 17 char[] Sc = S.toCharArray(); 18 char[] Tc = T.toCharArray(); 19 20 p[0][0] = Tc[0] == Sc[0] ? 1:0; 21 22 for(int i=1;i<S.length();i++) 23 p[0][i] = p[0][i-1]+(Tc[0] == Sc[i]?1:0); 24 25 for(int j = 1;j<T.length();j++) 26 p[j][0] = 0; 27 28 for(int i=1;i<T.length();i++){ 29 for(int j=1;j<S.length();j++){ 30 p[i][j] = p[i][j-1]+(Tc[i] == Sc[j] ? p[i-1][j-1]:0); 31 } 32 } 33 return p[T.length()-1][S.length()-1]; 34 } 35 /** 36 * O(n) space complexity solution 37 * @param S 38 * @param T 39 * @return 40 */ 41 public int numDistinct2(String S,String T){ 42 if(S.length()<T.length()) 43 return 0; 44 int[] p = new int[S.length()]; 45 //for convenient 46 char[] Sc = S.toCharArray(); 47 char[] Tc = T.toCharArray(); 48 49 p[0] = Tc[0] == Sc[0] ? 1:0; 50 51 for(int i=1;i<S.length();i++) 52 p[i] = p[i-1]+(Tc[0] == Sc[i]?1:0); 53 54 for(int i=1;i<T.length();i++){ 55 for(int j=S.length()-1;j>=0;j--){ 56 p[j] = p[j] + (Tc[i] == Sc[j]? p[j-1] :0); 57 } 58 } 59 return p[S.length()-1]; 60 61 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。