问题描述:
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
.
原问题链接:https://leetcode.com/problems/distinct-subsequences/
问题分析
这个问题相对来说比较难找到思路。对于给定的源串s来说,要让它的子串能够构成目标串t,那么理论上可能是它里面的任何一个元素可能存在或者删除。如果按照这个思路,假设源串长度为m的话,那么对它里面每种情况进行构造并和目标串比较的可能性有2 ** m次。这种情况将使得解决方法不可接受。因此,我们需要根据原来的问题描述来寻找一个它们关系推导的规律。
假设对于s来说,它的当前位置为i,对于t来说它的当前位置为j。那么当s.charAt(i) != t.charAt(j)的时候,说明s串里i这个位置的元素必须被删除才行,否则没法匹配。这个时候它们的可能构成数量和s[i - 1], t[j]的值相同。那么,当s.charAt(i) == t.charAt(j)的话呢?那么s[i - 1], t[j - 1]的情况是一种选择。而s[i - 1], t[j]也是一种选项。这个地方有点难以理解,为什么s[i - 1], t[j]也是一种选项呢?因为我们在前面的问题定义里,对于s来说它里面每个元素可能存在也可能删除。那么当删除第i个元素的时候,也有可能它前面的i - 1个元素和t中间的j个元素也构成了符合条件的序列,所以这种情况也应该包含进来。
按照这个思路,我们可以定义一个二维矩阵int[][] matrix,它是一个(m + 1) x (n + 1)的矩阵。在最开始的时候,其中m, n分别表示s和t的长度。matrix[][]里有一个初始条件,就是matrix[i][0] = 1。就是说,对于任意长度的源串s,对应于一个空串t来说,它都有一个子串,也就是删除它所有的字符。而对于其他的情况,则按照我们前面讨论的针对s.charAt(i - 1) == t.charAt(j - 1)的情况来处理。
于是我们可以得到如下的代码实现:
public class Solution { public int numDistinct(String s, String t) { int m = s.length(); int n = t.length(); if(n > m) return 0; int[][] matrix = new int[m + 1][n + 1]; for(int i = 0; i <= m; i++) matrix[i][0] = 1; for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { matrix[i][j] = matrix[i - 1][j] + (s.charAt(i - 1) == t.charAt(j - 1) ? matrix[i - 1][j - 1] : 0); } } return matrix[m][n]; } }
这种实现的时间复杂度和空间复杂度基本上都是O(m * n) 。
改进
在上述的代码实现中,我们还有一个可以改进的细节,就是对于空间的使用。前面的二维数组可以缩小为一维的数组,因为我们这里只需要保留t里面对应每个长度的匹配个数,我们可以重用之前的结果。
这种方式实现的代码如下:
public class Solution { public int numDistinct(String s, String t) { int m = t.length(); int n = s.length(); if(m > n) return 0; int[] path = new int[m + 1]; path[0] = 1; for(int j = 1; j <= n; j++) { for(int i = m; i >= 1; i--) { path[i] = path[i] + (t.charAt(i - 1) == s.charAt(j - 1) ? path[i - 1] : 0); } } return path[m]; } }
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
Leetcode:Leetcode提交
LeetCode 101:和你一起你轻松刷题(C++)
leetcode:leetcode刷题
加油站问题leetcode LeetCode LeetCode-JS分类列表: :smiling_face_with_smiling_eyes: :flushed_face: :winking_face: :face_with_tongue: :face_with_open_mouth: :beaming_face_with_smiling_...
LeetCode:LeetCode的代码
Leetcode:LeetCode解题代码
LeetCode:LeetCode的注释
leetcode:LeetCode问题
leetcode:LeetCode题解