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
.
public class Solution { public int numDistinct(String S, String T) { if (S==null || T==null || S.length()<T.length() || (S.length() == T.length() && !S.equals(T))) return 0; int counter = 0; char[] s = S.toCharArray(); char[] t = T.toCharArray(); return loopAndMatch(s, 0, t, 0); } public int loopAndMatch(char[] s, int start, char[] t, int index) { if (start >= s.length || index >= t.length) { return 0; } int counter = 0; char target = t[index]; for (int i=start; i<s.length; i++) { if (s[i]==target) { if (index == t.length-1) counter++; else counter += loopAndMatch(s, i+1, t, index+1); } } return counter; } }
相关推荐
Distinct Subsequences烟雨迷楼1
115.Distinct_Subsequences不同的子序列【LeetCode单题讲解系列】
1.三角形找一条从顶到底的最小路径 2.最大子数组和 3.回文最小划分次数 4.最佳时间买卖股票 5. 判断字符串s3是否由s1,s2交叉存取组成 ...9. 不同的子序列Distinct Subsequences 10.单词分解Word Break
Subsequences](./leetcode/动态规划-Distinct Subsequences.java) [动态规划-Longest Valid Parentheses](./leetcode/动态规划-Longest Valid Parentheses.java) [动态规划-Maximum Length of Repeated Subarray](./...
leetcode 分类 LeetCode Progress 128/154 Other Solutions ...Subsequences Decode Ways Palindrome Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
Distinct Subsequences Word Break Word Break II Dungeon Game House Robber House Robber II House Robber III Range Sum Query - Immutable Range Sum Query 2D - Immutable 图 Clone Graph 位操作 Reverse Bits ...
115.Distinct Subsequences 2017/04/24 (Lintcode)92.Backpack, (Lintcode)125.Backpack II, (Lintcode)564.Backpack VI 不适用 53.Maximum Subarray, 91.Decode Ways, 96.Unique Binary Search Tree, 120.Triangle,...
leetcode卡 OJ 题目汇总 记录下自己做过的oj题目, 也记录下自己对算法以及编程的理解与...Subsequences两种解法解题失败 [] 2014-06-14-13:00 ~ 2014-06-14-14:40 Interleaving String动态规划解决, Recovering BST失败
java lru leetcode ##Thinking in Java chapter21 ##Netty in Action ####chapter2: ...Subsequences] () [Rotate Image] () [Ugly Number] () [Ugly Number II] () [Repeated DNA Sequences] () [Lar
不同的子序列 给定两个字符串s和t,返回等于t的s的不同子序列数。 字符串的子序列是通过删除某些字符(可以是无字符)而不会干扰其余字符的相对位置而从原始字符串形成的新字符串。 (即,“ ACE”是“ ABCDE”的子...
gas station leetcode 在牛客网上的在线编程中的leetcode在线编程题解 代码中有详细题解 完成: 树 Minimum Depth ...distinct-subsequences 递归 valid-palindrome 模拟 pascals-triangle 模拟 pasca