`
dugu108
  • 浏览: 23287 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

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.

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

    Distinct Subsequences烟雨迷楼1

    115.Distinct Subsequences不同的子序列【LeetCode单题讲解系列】

    115.Distinct_Subsequences不同的子序列【LeetCode单题讲解系列】

    常见动态规划问题总结

    1.三角形找一条从顶到底的最小路径 2.最大子数组和 3.回文最小划分次数 4.最佳时间买卖股票 5. 判断字符串s3是否由s1,s2交叉存取组成 ...9. 不同的子序列Distinct Subsequences 10.单词分解Word Break

    javalruleetcode-learn-algorithms::laptop:Java实现的各种算法题解

    Subsequences](./leetcode/动态规划-Distinct Subsequences.java) [动态规划-Longest Valid Parentheses](./leetcode/动态规划-Longest Valid Parentheses.java) [动态规划-Maximum Length of Repeated Subarray](./...

    leetcode分类-LeetCode:力码

    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

    cpp-算法精粹

    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 ...

    gasstationleetcode-leetcode:LeetcodeOJ解决方案

    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卡-ojs:ojs

    leetcode卡 OJ 题目汇总 记录下自己做过的oj题目, 也记录下自己对算法以及编程的理解与...Subsequences两种解法解题失败 [] 2014-06-14-13:00 ~ 2014-06-14-14:40 Interleaving String动态规划解决, Recovering BST失败

    javalruleetcode-magician:java学习

    java lru leetcode ##Thinking in Java chapter21 ##Netty in Action ####chapter2: ...Subsequences] () [Rotate Image] () [Ugly Number] () [Ugly Number II] () [Repeated DNA Sequences] () [Lar

    Distinct-Subsequences-

    不同的子序列 给定两个字符串s和t,返回等于t的s的不同子序列数。 字符串的子序列是通过删除某些字符(可以是无字符)而不会干扰其余字符的相对位置而从原始字符串形成的新字符串。 (即,“ ACE”是“ ABCDE”的子...

    gasstationleetcode-leetcode-in-niuke:在牛客网上的在线编程中的leetcode在线编程题解

    gas station leetcode 在牛客网上的在线编程中的leetcode在线编程题解 代码中有详细题解 完成: 树 Minimum Depth ...distinct-subsequences 递归 valid-palindrome 模拟 pascals-triangle 模拟 pasca

Global site tag (gtag.js) - Google Analytics