当前位置:网站首页>Simulation volume leetcode [general] 1143 Longest common subsequence
Simulation volume leetcode [general] 1143 Longest common subsequence
2022-07-06 06:17:00 【Encounter simulation volume】
1143. Longest common subsequence
Given two strings text1 and text2, Returns the longest of these two strings Common subsequence The length of . If it doesn't exist Common subsequence , return 0 .
A string of Subsequence This is a new string : It is to delete some characters from the original string without changing the relative order of the characters ( You can also delete no characters ) After the composition of the new string .
for example ,“ace” yes “abcde” The subsequence , but “aec” No “abcde” The subsequence .
Two strings of Common subsequence Is the subsequence shared by these two strings .
Example 1:
Input :text1 = “abcde”, text2 = “ace”
Output :3
explain : The longest common subsequence is “ace” , Its length is 3 .
Example 2:
Input :text1 = “abc”, text2 = “abc”
Output :3
explain : The longest common subsequence is “abc” , Its length is 3 .
Example 3:
Input :text1 = “abc”, text2 = “def”
Output :0
explain : The two strings have no common subsequence , return 0 .
Tips :
1 <= text1.length, text2.length <= 1000
text1 and text2 It only consists of lowercase English characters .
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/longest-common-subsequence
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Code :
from leetcode_python.utils import *
class Solution:
def __init__(self):
pass
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
length1,length2 = len(text1),len(text2)
if 0==length1 and 0==length2:return 0
this_dp = [0]*(length1+1)
for to_word2 in range(length2+1):
last_dp = this_dp.copy()
for from_word1 in range(length1+1):
if 0==from_word1 or 0==to_word2:
this_dp[from_word1] = 0
elif text1[from_word1-1]==text2[to_word2-1]:
this_dp[from_word1] = last_dp[from_word1-1] + 1
else:
this_dp[from_word1] = max(this_dp[from_word1 - 1], last_dp[from_word1])
print(f'to w2[{
to_word2}-1], {
this_dp}')
return this_dp[-1]
def minDistance_583_ Deletion of two strings (self, word1: str, word2: str) -> int:
length1,length2 = len(word1),len(word2)
if 0==length1 and 0==length2:return 0
this_dp = [0]*(length1+1) # word1 Each letter of to word2 The number of times each letter needs to be deleted
for to_word2 in range(length2+1):
last_dp = this_dp.copy()
for from_word1 in range(length1+1):
if 0==from_word1 or 0==to_word2: # consider word1 Delete to 0 The situation of
this_dp[from_word1] = from_word1 + to_word2
elif word1[from_word1-1]==word2[to_word2-1]:
this_dp[from_word1] = last_dp[from_word1-1]
else:
this_dp[from_word1] = min(this_dp[from_word1 - 1], last_dp[from_word1]) + 1
print(f'to w2[{
to_word2}-1], {
this_dp}')
return this_dp[-1]
def test(data_test):
s = Solution()
return s.longestCommonSubsequence(*data_test)
def test_obj(data_test):
result = [None]
obj = Solution(*data_test[1][0])
for fun, data in zip(data_test[0][1::], data_test[1][1::]):
if data:
res = obj.__getattribute__(fun)(*data)
else:
res = obj.__getattribute__(fun)()
result.append(res)
return result
if __name__ == '__main__':
datas = [
["abcde","ace"],
["abc","abc"],
["abc","def"],
]
for data_test in datas:
t0 = time.time()
print('-' * 50)
print('input:', data_test)
print('output:', test(data_test))
print(f'use time:{
time.time() - t0}s')
remarks :
GitHub:https://github.com/monijuan/leetcode_python
CSDN Summary : Simulation volume Leetcode Summary of questions _ Paper blog -CSDN Blog
You can add QQ Group communication :1092754609
leetcode_python.utils See the description on the summary page for details
First brush questions , Then generated by script blog, If there is any mistake, please leave a message , I see it will be revised ! thank you !
边栏推荐
猜你喜欢
Manhattan distance sum - print diamond
【微信小程序】搭建开发工具环境
[API interface tool] Introduction to postman interface
Left matching principle of joint index
Summary of anomaly detection methods
JWT-JSON WEB TOKEN
[C language] string left rotation
Hypothesis testing learning notes
ESP32 ESP-IDF看门狗TWDT
Function of contenttype
随机推荐
LeetCode 732. 我的日程安排表 III
[API interface tool] Introduction to postman interface
Still worrying about how to write web automation test cases? Senior test engineers teach you selenium test case writing hand in hand
How to extract login cookies when JMeter performs interface testing
数字三角形模型 AcWing 1015. 摘花生
[web security] nodejs prototype chain pollution analysis
数学三大核心领域概述:几何
Amazon Engineer: eight important experiences I learned in my career
D - How Many Answers Are Wrong
10M25DCF484C8G(FPGA) AMY-6M-0002 BGA GPS模块
An article was uncovered to test the truth of outsourcing companies
Leaflet map
Isam2 operation process
调用链监控Zipkin、sleuth搭建与整合
php使用redis实现分布式锁
通过修改style设置打印页样式
Basic knowledge of error
Buuctf-[[gwctf 2019] I have a database (xiaoyute detailed explanation)
Online and offline problems
Manage configuration using Nacos