Distinct Subsequences @ LeetCode (Python)
kitt
posted @ 2014年3月15日 20:04
in LeetCode
, 2803 阅读
动态规划，写出二维数组的表达式后会发现dp[i][j]只和dp[i-1][j]、dp[i-1][j-1]有关，所以可以进一步简化为一维数组，感谢traceformula的留言。
# 63 tests，132 ms
class Solution(object):
def numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
# Let dp[i][j] be number of distinct subsequences for first i letters of s, first j letters of t
# if s[i - 1] != t[j - 1], then dp[i][j] = dp[i - 1][j]
# if s[i - 1] == t[j - 1], then dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
# based on this, we can just use one-dimension dp array:
# len(dp) = len(t) + 1, dp[0] = 1
# if s[i - 1] == t[j - 1], then dp[j] = dp[j] + dp[j - 1], 1 <= j <= len(t)
lenS, lenT = len(s), len(t)
dp = [0 for i in xrange(lenT + 1)]
dp[0] = 1
for i in xrange(lenS):
for j in reversed(xrange(1, lenT + 1)):
if s[i] == t[j - 1]:
dp[j] = dp[j] + dp[j - 1]
return dp[lenT]
2015年8月27日 15:40
I have a solution here using less space:
public class Solution {
public int numDistinct(String s, String t) {
if(s == null || t == null || t.length() == 0) return 0;
int[] dp = new int[t.length()];
for(int i = 0; i<s.length(); i++){
char c = s.charAt(i);
for(int j=dp.length-1; j>=0; j--){
if(c == t.charAt(j)){
dp[j] = dp[j] + (j!=0?dp[j-1]: 1);
}
}
}
return dp[t.length()-1];
}
}
URL(http://traceformula.blogspot.com/2015/08/distinct-subsequences.html )
2015年8月30日 14:27
已更新，多谢哈~@traceformula: