首页 > 代码库 > Leetcode: Distinct Subsequences
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.
最早尝试的是recursion的做法，大集合的时候TLE了。想想肯定会的，我的算法相当于在穷举S所有元素组成的子集，找到其中与T相等的次数，算法复杂度为O（2^N）, exponential了，不TLE才怪。想的太naive了。
1 import java.util.*; 2 3 public class Solution { 4 public int numDistinct(String S, String T) { 5 if (S.equals(T)) return 1; 6 if (S.length() < T.length()) return 0; 7 boolean[] visited = new boolean[S.length()]; 8 StringBuffer tt = new StringBuffer(T); 9 StringBuffer current = new StringBuffer();10 int count = 0;11 numCount(S, tt, current, count, visited);12 return count;13 }14 15 public void numCount(String s, StringBuffer tt, StringBuffer current, int count, boolean[] visited) {16 if (current.equals(tt)) {17 count += 1;18 return;19 }20 for (int i = 0; i < s.length(); i++) {21 if (!visited[i]) {22 char c = s.charAt(i);23 current.append(c);24 visited[i] = true;25 numCount(s, tt, current, count, visited);26 current.deleteCharAt(current.length() - 1);27 visited[i] = false;28 }29 }30 }31 }
肯定得用DP，想了想感觉很难上手，后来看了别人的思路：
（以S="rabbbit",T = "rabbit"为例）：
r a b b b i t
1 1 1 1 1 1 1 1
r 0 1 1 1 1 1 1 1
a 0 0 1 1 1 1 1 1
b 0 0 0 1 2 3 3 3
b 0 0 0 0 1 3 3 3
i 0 0 0 0 0 0 3 3
t 0 0 0 0 0 0 0 3
Let W(i, j) stand for the number of subsequences of S(0, i) in T(0, j). If S.charAt(i) == T.charAt(j), W(i, j) = W(i-1, j-1) + W(i-1,j); Otherwise, W(i, j) = W(i-1,j).
1 public class Solution { 2 public int numDistinct(String S, String T) { 3 int[][] table = new int[S.length() + 1][T.length() + 1]; 4 5 for (int i = 0; i < S.length(); i++) 6 table[i][0] = 1; 7 8 for (int i = 1; i <= S.length(); i++) { 9 for (int j = 1; j <= T.length(); j++) {10 if (S.charAt(i - 1) == T.charAt(j - 1)) {11 table[i][j] += table[i - 1][j] + table[i - 1][j - 1];12 } else {13 table[i][j] += table[i - 1][j];14 }15 }16 }17 18 return table[S.length()][T.length()];19 }20 }
Leetcode: Distinct Subsequences
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。