精华内容
下载资源
问答
  • leetcode 最长公共子串

    2020-04-03 21:34:22
    leetcode 最长公共子串 题目描述:给定两个字符串,求出他们之间最长相同子字符串长度。 解题步骤:采用动态规划,与求解最长公共子序列类似,只不过状态定义要修改。 1、 状态定义:dp[i][j]表示以s1[i]和s2[j]为...

    leetcode 最长公共子串


    题目描述:给定两个字符串,求出他们之间最长相同子字符串长度。
    解题步骤:采用动态规划,与求解最长公共子序列类似,只不过状态定义要修改。
    1、 状态定义:dp[i][j]表示以s1[i]和s2[j]为最后一个元素的最长公共子串,如果最长公共子串存在,公共子串的最后一个元素一定是s1[i]或者s2[j]他们相等。
    2、 状态转移方程
    如果s1[i]和s2[j]相等,那么:dp[i][j] = dp[i-1][j-1]+1;
    如果s1[i]和s2[j]不相等,则:dp[i][j] = 0;
    3、 初始化:初始dp[0][j]和dp[i][0]都为false
    4、 输出:dp[i][j]的最大值
    代码

    	public int longestCommonString(String s1,String s2) {
    		int[][] dp = new int[s1.length()+1][s2.length()+1];
    		int maxlen = 0;
    		for (int i = 1; i <= s1.length(); i++) {
    			for (int j = 1; j <= s2.length(); j++) {
    				if(s1.charAt(i-1)==s2.charAt(j-1))
    					dp[i][j] = dp[i-1][j-1]+1;
    				else
    					dp[i][j] = 0;
    				maxlen = Math.max(maxlen, dp[i][j]);
    			}
    		}
    		return maxlen;
    	}
    
    展开全文
  • LeetCode 最长公共子串

    2020-05-05 15:02:57
    其实这道题的思路很简单,就是将第一个字符串作为源字符串,然后将其与剩下的字符串逐一比较,找出相同的字符串。另外就是注意如果字符串数组是否为空。主要是实现方式的区别。 在这道题中我知道了迭代器的用法,这...

    在这里插入图片描述
    其实这道题的思路很简单,就是将第一个字符串作为源字符串,然后将其与剩下的字符串逐一比较,找出相同的字符串。另外就是注意如果字符串数组是否为空。主要是实现方式的区别。
    在这道题中我知道了迭代器的用法,这是我没注意的,之后写个博客。
    另外就是substr函数。这是一个复制字符串函数,刚开始我还以为是切割字符串函数。它的作用是复制自定义长度的字符串。
    代码就不贴了,毕竟自己实现的方式太复杂了 。 唉 惭愧

    展开全文
  • leetcode 最长公共子串 python 给定两个字符串str1和str2,输出两个字符串的最长公共子串 题目保证str1和str2的最长公共子串存在且唯一。 class Solution: def LCS(self , str1 , str2 ): # write code here s1,s2...

    leetcode 127 最长公共子串 python

    给定两个字符串str1和str2,输出两个字符串的最长公共子串 题目保证str1和str2的最长公共子串存在且唯一。

    class Solution:
        def LCS(self , str1 , str2 ):
            # write code here
            s1,s2='',''
            for i in str1:
                s1=s1+i
                if s1 in str2:
                    if len(s1)>len(s2):
                        s2=s1
                else:
                    s1=s1[1:]
            return s2
    
    展开全文
  • Leetcode 最长回文子串

    2020-07-22 11:08:14
    题目描述 找出给出的字符串S中最长的回文子串。假设S的最大长度为1000,并且只存在唯一解。... 那么最长公共子串,即寻找二维数组中 最长的对角线为1的长度 进一步优化 若匹配时 dp[i][j]=dp[i-1][j-...

    题目描述

    找出给出的字符串S中最长的回文子串。假设S的最大长度为1000,并且只存在唯一解。

     

    示例1

    输入

    复制

    "abcba"

    输出

    复制

    "abcba"

     

    思路:

    将原先s1 反转得到s2

    求解s1与s2的最长公共子串

    求解最长公共子串方法

    动态规划 dp

    • dp[i][j]表示s1[i]与s2[j]匹配关系 若不等置为0 否则置为1  
    • 那么最长公共子串,即寻找二维数组中 最长的对角线为1的长度
    • 进一步优化 若匹配时  dp[i][j]=dp[i-1][j-1]+1  即一旦匹配,利用上之前对角线的数值  在此基础上++
    • 一旦长度更大,记录下index下标以及更新max
    int dp[1001][1001];
        
        //最长公共子串长度
        string max_fun(string s1,string s2)
        {
            int _max=0;
            for(int i=0;i<1001;i++)
            {
                dp[0][i]=0;
                dp[i][0]=0;
            }
            int index=-1;
            for(int i=0;i<s1.size();i++)
                for(int j=0;j<s2.size();j++)
                {
                    if(s1[i]==s2[j])
                    {
                        dp[i+1][j+1]=dp[i][j]+1;
                        if(dp[i+1][j+1]>_max)
                        {
                            _max=dp[i+1][j+1];
                            index=i;
                            
                        }
                       
                    }
                    else
                        dp[i+1][j+1]=0;
                    
                }
            
            
            return s1.substr(index-_max+1,_max);
            
            
        }
    
        
        string longestPalindrome(string s) {
            // write code here
            if(s.size()==0)
                return string("");
            if(s.size()==1)
                return s;
            string s2=s;
            reverse(s2.begin(), s2.end());
            return max_fun(s, s2);
            
            
        }

     

    展开全文
  • 我觉得这类问题和最长公共子串和最长公共子序列有些相似,当然都是用dp的思想. 但是,*肯定不能通过用逆转串来转化为最长公共子串和最长公共子序列 *来解决问题. Leetcode516 最长回文子序列(已经注释非常清晰) class ...
  • leetcode 最长回文子串

    2019-07-10 19:28:35
    1.可用求字符串和其逆序字符串的最长公共子串的方式求解。 2.还需改进,防止“aacfcaa”这种情况出现。只需要在更新max之前判断两个字符串的起始位置的索引是否相同,即下标和为母串长度。 class Solution { ...
  • leetcode最长回文子串c++

    千次阅读 2019-04-08 11:54:25
    最长回文子串 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1: 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2: 输入: "cbbd" 输出: "bb" ...
  • LeetCode最长回文子串

    2019-08-31 00:00:00
    给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1: 输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。 示例 2: 输入: "cbbd"输出: "bb" ...
  • 最长回文子串 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 输入: "cbbd" 输出: "bb" 思路 暴力求解 暴力求解...
  • 作者:windliang 链接:https://leetcode-cn.com/problems/two-sum/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-bao-gu/ 来源:力扣(LeetCode) ...给定一个字符串 s,找到 s 中最长的回文子串。你...
  • Leetcode最长公共子串

    千次阅读 2018-10-17 11:12:22
    编写一个函数来查找字符串数组中最长公共前缀字符串。 如果没有公共前缀,则返回空字符串""。 例1: 输入: ["flower","flow","flight"] 输出: “fl” 例2: ...
  • 子序列与子串的区别: 假设有S1 = “abcdeffg” S2 = "abcfg" 子串:“abc” 子序列:“abcfg” 简单的说,子串就是需要连续,...给两个整数数组A和B,返回两个数组中公共的、长度最长的子数组的长度。 示例 1:...
  • 给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。 示例1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无...
  • leetcode14:最长公共子串: 笨拙的原始解法,编程中遇到太多的bug,觉得有很多边界问题 func longestCommonPrefix(strs []string) string { if len(strs) <1 { return "" } rune_strs :=make([][]rune,...
  • 可以使用第一个字符串与第二个字符串进行最长公共子串的匹配,再用这个最长公共子串和后面的字符串进行匹配,如果匹配到的子串为空,则最长公共子串一定为空。 class Solution { public String longestCommonPrefix...
  • LeetCode 最长公共子序列和子串

    千次阅读 2019-08-06 10:39:13
    求两个字符串的最长公共子串(Longest Common Substring)和最长公共子序列(Longest Common Subsequence)的区别在于 最长公共子串是在原来的字符串中是连续的,而子序列只需要保持相对顺序一致,并不要求连续。 例如...
  • 最长公共子串 在说回文子串之前,先来说说最长公共子...LeetCode718就是一道最长公共子串的题目。 题目地址:https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/ class Solution { public int fi
  • Leetcode 最大回文子串

    2020-09-01 16:14:13
    题目描述 对于一个字符串,请设计一个高效算法,计算其中最长回文子串的长度。...1234694321 该串最大回文子串长度为1 但是翻转之后最大公共子串长度为4 思路: 采取动态规划方式 dp[i][j]表示str[i....
  • LeetCode-最长回文子串

    2020-01-08 23:10:41
    题目链接:最长回文子串 给定一个字符串 s,找到 s 中最长的回文子串。 解法一:暴力解法 ...那么把原来的字符串 s 反过来得到 reverse_s,找到它们的最长公共子串是不是就是满足条件的回文子串...
  • 给定两个字符串text1 和text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。 一个字符串的子序列是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些...
  • leetcode-最长回文子串

    2020-05-21 09:39:47
    也是看了大佬的解答,因为回文是从前往后读以及从后往前读都是一样的所以采用寻找最长公共子串的方法(注意不是经常使用动态规划寻找的最长公共子序列),公共子串同样采用动态规划的思想,寻找最长公共子串。...
  • 更多LeetCode题解 我的解法 O ( n 3 ) O(n^3) O ( n 3 ) Time Limit Exceeded,大家看看就好了,不是好的解法。暴力解法,其实质就是找出所有的i,j并查看是否为回文串,只不过使用了find_last_of(s[i])跳过了...
  • 最近BAT等一线大厂面试的热门题目,就是求最长公共子串子序列问题,Leetcode上面没有完全相同的题目,但是有类似的题目,让我们一起来看看。 1.leetcode#718. Maximum Length of Repeated Subarray 1.1题目...
  • 1、最长公共子串 首先看最长公共子串的解答(暴力算法、动态规划、) 从优化到再优化,最长公共子串 2、最长公共子序列(LCS)  解析:动态规划解最长公共子序列问题 3、 leetcode 5 Longest Palindromic ...
  • 最长公共子串

    2020-10-26 02:02:36
    题目 ...动态规划经典例题——最长公共子序列和最长公共子串 最长公共子串(动态规划) 解答 /** * 最长公共子串 * @param s * @param t * @return */ public static int getLCS(String s, Str
  • 1. 最长公共子序列(LCS) 1.1 问题描述 1.2 思路 利用动态规划。 下一步就要找到状态之间的转换方程。 因此可以根据这个方程来进行填表,以"helloworld"和“loop”为例: 1.3 代码 def LCS(string1,string2...
  • =1e5)个串的最长公共子串的长度, 字符集大小1e5,k个串的总长度不超过1e5 思路来源 乱搞AC 题解 大概是一个poj3294的后缀数组原题, 首先将k个串用k-1个特殊字符(这里用1e5+1)连接到一起, 注意不能用k个,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,273
精华内容 1,309
关键字:

leetcode最长公共子串