fork download
copy 
  1. def solve(s,t,i,j,dp):
  2.     if (i,j) in dp:
  3.         return dp[(i,j)]
  4.     if i>=len(s) and j>=len(t):
  5.         return 1
  6.     if j>=len(t):
  7.         return 1
  8.     if i>=len(s):
  9.         return 0
  10.     ans=solve(s,t,i+1,j,dp)
  11.     if s[i]==t[j]:
  12.         ans+=solve(s,t,i+1,j+1,dp)
  13.     dp[(i,j)]=ans
  14.     return ans
  15.  
  16. class Solution:
  17.     def numDistinct(self, s: str, t: str) -> int:
  18.         dp={}
  19.         n=len(s)
  20.         m=len(t)
  21.         dp=[[0]*(m+1) for x in range(2)]
  22.         dp[0][0]=1
  23.         for x in range(2):
  24.             dp[x][0]=1
  25.         flag=0
  26.         for i in range(1,len(s)+1):
  27.             for j in range(1,len(t)+1):
  28.                 if s[i-1]==t[j-1]:
  29.                     dp[flag][j]=dp[flag^1][j-1]+dp[flag^1][j]
  30.                 else:
  31.                     dp[flag][j]=dp[flag^1][j]
  32.             flag=flag^1
  33.         return dp[flag^1][m]
Success #stdin #stdout 0.02s 9112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/42LfJr
language:
Python 3 (python  3.9.5)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!