python">class Solution : def numDistinct ( self, s: str , t: str ) - > int : n1 = len ( s) n2 = len ( t) dp = [ [ 0 ] * ( n1 + 1 ) for _ in range ( n2 + 1 ) ] for j in range ( n1 + 1 ) : dp[ 0 ] [ j] = 1 for i in range ( 1 , n2 + 1 ) : for j in range ( 1 , n1 + 1 ) : if t[ i - 1 ] == s[ j - 1 ] : dp[ i] [ j] = dp[ i - 1 ] [ j - 1 ] + dp[ i] [ j - 1 ] else : dp[ i] [ j] = dp[ i] [ j - 1 ] return dp[ - 1 ] [ - 1 ]
python">class Solution : def minDistance ( self, word1: str , word2: str ) - > int : m, n = len ( word1) , len ( word2) dp = [ [ 0 ] * ( n + 1 ) for _ in range ( m + 1 ) ] for i in range ( m) : for j in range ( n) : if word1[ i] == word2[ j] : dp[ i+ 1 ] [ j+ 1 ] = dp[ i] [ j] + 1 else : dp[ i+ 1 ] [ j+ 1 ] = max ( dp[ i] [ j+ 1 ] , dp[ i+ 1 ] [ j] ) return m + n - dp[ m] [ n] * 2
python">class Solution : def minDistance ( self, word1: str , word2: str ) - > int : n = len ( word1) m = len ( word2) if n * m == 0 : return n + mD = [ [ 0 ] * ( m + 1 ) for _ in range ( n + 1 ) ] for i in range ( n + 1 ) : D[ i] [ 0 ] = ifor j in range ( m + 1 ) : D[ 0 ] [ j] = jfor i in range ( 1 , n + 1 ) : for j in range ( 1 , m + 1 ) : left = D[ i - 1 ] [ j] + 1 down = D[ i] [ j - 1 ] + 1 left_down = D[ i - 1 ] [ j - 1 ] if word1[ i - 1 ] != word2[ j - 1 ] : left_down += 1 D[ i] [ j] = min ( left, down, left_down) return D[ n] [ m]