首页 > 代码库 > LeetCode 115 Distinct Subsequences
LeetCode 115 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
.
思路1:回溯法,结果TLE
public class Solution { public static int counter = 0; public int numDistinct(String S, String T) { counter = 0; Distinct(S, T); return counter; } public void Distinct(String S, String T) { if (T.length() > 0) { Pattern p = Pattern.compile(T.substring(0, 1)); Matcher m = p.matcher(S); while (m.find()) { Distinct(S.substring(m.start() + 1), T.substring(1)); } } else { counter++; } } }思路2:动态规划,用二维数组result[T.length() + 1][S.length() + 1]来存储T.subString(0,i)在S.subString(0,j)的数目,
如果T.charAt(i - 1) == S.charAt(j - 1)则 result[i][j] = result[i - 1][j - 1] + result[i][j - 1];
否则result[i][j] = result[i][j - 1];
不过要先算一下T.charAt(0) == S.charAt(i-1)若成立,则result[1][i] = result[1][i - 1] + 1;否则result[1][i] = result[1][i - 1];
public class Solution { public int numDistinct(String S, String T) { int[][] result = new int[T.length() + 1][S.length() + 1]; for (int i = 1; i <=S.length(); i++) { if (T.charAt(0) == S.charAt(i-1)) { result[1][i] = result[1][i - 1] + 1; } else { result[1][i] = result[1][i - 1]; } } for (int i = 2; i <= T.length(); i++) { for (int j = 1; j <= S.length(); j++) { if (T.charAt(i - 1) == S.charAt(j - 1)) result[i][j] = result[i - 1][j - 1] + result[i][j - 1]; else result[i][j] = result[i][j - 1]; } } return result[T.length()][S.length()]; } }
LeetCode 115 Distinct Subsequences
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。