1143. Longest Common Subsequence
2024-09-02 11:20:10
Description:
Given two strings text1
and text2
, return the length of their longest common subsequence.
A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A common subsequence of two strings is a subsequence that is common to both strings.
If there is no common subsequence, return 0.
Solution:
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int: n1 = len(text1)
n2 = len(text2) dp = [[0 for i in range(n2+1)] for j in range(n1+1)]
for i in range(n1):
for j in range(n2):
if text1[i]==text2[j]:
dp[i][j] = 1 + dp[i-1][j-1]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) return dp[n1-1][n2-1]
Notes:
2-d Dynamic Programming
O(mn)
最新文章
- Discuz论坛安全加固浅析
- css让元素居中显示
- Unity3d《Shader篇》描边
- BZOJ3421 : Poi2013 Walk
- blend 从无到有系列之添加自定义Rectangle样式指定到资源文件
- jvm笔记
- phpcms如何嵌套循环
- 新建cocos2d-xproject
- css2.1实现圆角边框
- 如何开发由Create-React-App 引导的应用(三)
- 基本MVVM 和 ICommand用法举例(转)
- visual studio 中sstrcpy报错的问题
- [dev]typeof, offsetof 和container_of
- JAVA的单元测试技术
- css3图片旋转
- Fiddler 简单介绍
- 使用Ant发布web应用到tomcat
- linux性能分析工具之火焰图
- Part 2 - Fundamentals(4-10)
- 如何把高版本的sqlserver 还原到低版本的 sqlserver