- 技术博客
- [LeetCode Python3C++] 115. Distinct Subsequences
Python3 Solution:
class Solution:
def numDistinct(self
, s
: str, t
: str) -> int:
if not s
:
if t
:
return 0
return 1
ssize
, tsize
= len(s
), len(t
)
dp
= [[0]*(ssize
+1) for _
in range(tsize
+1)]
for i
in range(ssize
+1):
dp
[0][i
] = 1
for i
in range(1, tsize
+1):
for j
in range(1, ssize
+1):
if t
[i
-1] != s
[j
-1]:
dp
[i
][j
] = dp
[i
][j
-1]
else:
dp
[i
][j
] = dp
[i
][j
-1] + dp
[i
-1][j
-1]
return dp
[tsize
][ssize
]
C++ Solution:
class Solution {
public:
int numDistinct(string S
, string T
) {
if(S
.empty()){
if(T
.empty())
return 1;
return 0;
}
int n
= T
.size();
int m
= S
.size();
vector
<vector
<long>> vec(n
+1, vector
<long> (m
+1, 0));
for(int i
= 0; i
< m
; i
++){
vec
[0][i
] = 1;
}
for(int i
= 1; i
<= n
; i
++){
for(int j
= 1; j
<= m
; j
++){
if(T
[i
-1] != S
[j
-1]) vec
[i
][j
] = vec
[i
][j
-1];
else vec
[i
][j
] = vec
[i
][j
-1]+vec
[i
-1][j
-1];
}
}
return vec
[n
][m
];
}
};
