[LeetCode] 1143. 最長共通部分列

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

中くらい

2 つの文字列が与えられた場合 テキスト 1 そして テキスト2、戻る 彼らの最長の長さ 共通部分列. ない場合 共通部分列、戻る 0.

あ後続文字列のは、残りの文字の相対的な順序を変更せずに、一部の文字 (なくてもよい) を削除して、元の文字列から生成された新しい文字列です。

例えば、 "エース" の続きです 「アブデ」.

あ 共通部分列 2 つの文字列のは、両方の文字列に共通する部分シーケンスです。

例 1:

入力： text1 = "abcde"、text2 = "エース" 
出力： 3  
説明： 最も長い共通部分列は「ace」で、その長さは 3 です。

例 2:

入力： テキスト1 = "abc"、テキスト2 = "abc"
出力： 3
説明： 最も長い共通部分列は「abc」で、その長さは 3 です。

例 3:

入力： テキスト1 = "abc"、テキスト2 = "def"
出力： 0
説明： このような共通の部分列は存在しないため、結果は 0 になります。

制約:

1 <= text1.length、text2.length <= 1000
テキスト 1 そして テキスト2 小文字の英字のみで構成されています。

パイソン

				
					# 時間計算量: O(n*m) # 空間計算量: O(n*m) クラス 解決策: def longestCommonSubsequence(self, text1: str, text2: str) -> int: dpGrid = [[0] * (len( text2) + 1) for _ in range(len(text1)+1)] forcol in reversed(range(len(text2))): for row in reversed(range(len(text1))): if text2[col ] == text1[row]: dpGrid[row][col] = 1 + dpGrid[row+1][col+1] else: dpGrid[row][col] = max( dpGrid[row+1][col] , dpGrid[row][col+1]) return dpGrid[0][0] text1 = "abcde" text2 = "ace" print(Solution().longestCommonSubsequence(text1, text2))

中くらい

パイソン

関連記事