115. Distinct Subsequences

115. Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

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.

思路： 截取"bbb" 和 “bb” 出来填表。

0 b b0 1 0 0b 1 1 0b 1 2 1b 1 3 3

class Solution { public int numDistinct(String s, String t) { int[][] table = new int[s.length() + 1][t.length() + 1]; for(int i=0; i

class Solution { public int numDistinct(String s, String t) { int sLength = s.length(); int tLength = t.length(); if (sLength < tLength) { return 0; } int[] row = new int[sLength + 1]; Arrays.fill(row, 1); int result; char tChar; for (int i = tLength - 1; i >= 0; i--) { result = 0; tChar = t.charAt(i); for (int j = sLength - tLength + i, index = sLength; j >= 0; j--, index--) { if (tChar == s.charAt(j)) { result += row[index]; } row[index] = result; } } return row[tLength]; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。