文档章节

Leetcode——最长不重复子串

wikison
 wikison
发布于 2015/08/19 14:29
字数 865
阅读 611
收藏 0

题:从一个字符串中找到一个连续子串,该子串中任何两个字符不能相同,求子串的最大长度并输出一条最长不重复子串。

自己的第一反应是使用动态规划来解决这个问题。在搜集资料之后,发现共有三种解决方案:

  1. 使用hash

  2. 使用DP + Hash

==================================================================

基本方法,使用简单Hash

其实判断重复问题最应该想到的是Hash,建立一个简单的hash table,key为字符的ASCII码值,value为该字符是否已经在当前子串中出现过(出现过为1,未出现为0)。最简单的方法就是对所有的子串进行查重,复杂度为θ(n^2)。

在扫描过程中,我们需要找到尽可能长的不重复子串,我称之为“极长不重复子串”。假设s[i...j]的当前的极长不重复子串为L(i,j),那么L(i, j+1)的长度分为两种情况:

    1. 上一个s[j+1]代表的字符出现在L(i.j)的起始位置之前,那么s[j+1]应该被添加到当前极长不重复子串中;

    2. 上一个s[j+1]代表的字符出现在L(i,j)的起始位置之后,那么记录下L(i,j),开始跟踪新的极长不重复子串。

在扫描完所有的str[0...n],str[1...n],str[2...n]....后,最长的极长字符串就是字长不重复子串

源代码为:

/* 最长不重复子串 设串不超过30
 * 我们记为 LNRS
 */
int maxlen;
int maxindex;
void output(char * arr);
 
/* LNRS 基本算法 hash */
char visit[256];
 
void LNRS_hash(char * arr, int size)
{
    int i, j;
    for(i = 0; i < size; ++i)
    {
        memset(visit,0,sizeof visit);
        visit[arr[i]] = 1;
        for(j = i+1; j < size; ++j)
        {
            if(visit[arr[j]] == 0)
            {
                visit[arr[j]] = 1;
            }else
            {
                if(j-i > maxlen)
                {
                    maxlen = j - i;
                    maxindex = i;
                }
                break;
            }
        }
        if((j == size) && (j-i > maxlen))
        {
            maxlen = j - i;
            maxindex = i;
        }
    }
    output(arr);
}

=========================================================================

使用DP+hash。使用DP以空间换时间的方法来解决此问题,DP最重要的思想就是要记录。

在第一种方法当中,我们扫面了所有的子串。但是如果str1是str2的子串,那么str1的最长不重复子串肯定小于或者等于str2。我们可以直接扫描整个给定的字符串,并在扫描过程中记录下所有扫描到极大字符串,找到最长的即可(仿照人工的思路)。

使用hash表来保存一个字符最近被扫描的时候所处的位置

代码如下:

class Solution 
{
public:
	int lengthOfLongestSubstring(string s) 
	{
		if (s.empty()) return 0;

		int visit[256];		//用来保存最近扫描到一个字符的位置
		int max_length;		//目前最大不重复子串的长度
		int start_index;	//目前最大不重复子串的起始索引
		int last_start;		//目前扫描的极大不重复子串的起始索引
		int last_length;	//目前扫描的极大不重复子串的长度

		start_index = 0;
		max_length = 0;
		last_start = 0;
		memset(visit, -1, sizeof(int) * 256);

		//第一个字符
		visit[s[0]] = 0;
		last_length = 1;

		for (int i = 1; i < s.size(); i++)
		{
			if (visit[s[i]] == -1)
			{
				last_length++;
				visit[s[i]] = i;
			}
			else if (visit[s[i]] < last_start)
			{
				last_length++;
				visit[s[i]] = i;
			}
			else
			{
				if (last_length > max_length)
				{
					max_length = last_length;
					start_index = last_start;
					last_start = visit[s[i]] + 1;		//更新当前极长子串的起点,是重复字符的后一位
					last_length = i - last_start + 1;
					visit[s[i]] = i;
				}
				else
				{
					last_start = visit[s[i]] + 1;
					last_length = i - last_start + 1;
					visit[s[i]] = i;
				}
			}
		}

		if (last_length > max_length)
		{
			max_length = last_length;
		}
		return max_length;
	}
};


© 著作权归作者所有

wikison
粉丝 1
博文 23
码字总数 11471
作品 0
闵行
私信 提问
算法题--无重复字符的最长子串

题目描述 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例 2: 输入: "...

独孤求媛
10/10
0
0
[leetcode] 5.最长回文子串

目录 [leetcode] 5.最长回文子串 回文 解法一:暴力求解法 解法二:改进的暴力求解法 解法三:马拉车算法 [leetcode] 5.最长回文子串 DATE: 2018-12-27 题目描述 给定一个字符串 ,找到 中最...

Cheehool
2018/12/27
0
0
Leetcode3——Longest Substring Without Repeating Characters

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. 问题描述 Given a string, find the length of the longest substring without repeating characters. Examples: 2. 求解 方法一 当遍......

Quincuntial
2017/04/01
0
0
[算法总结] 13 道题搞定 BAT 面试——字符串

本文首发于我的个人博客:尾尾部落 1. KMP 算法 谈到字符串问题,不得不提的就是 KMP 算法,它是用来解决字符串查找的问题,可以在一个字符串(S)中查找一个子串(W)出现的位置。KMP 算法把...

繁著
2018/09/05
0
0
C++双指针滑动和利用Vector实现无重复字符的最长子串—力扣算法

题目: 力扣原题链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/ 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入...

Foxer_Z
10/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

MongoDB系列-在复制集(replication)以及分片(Shard)中创建索引

关注我,可以获取最新知识、经典面试题以及微服务技术分享   在使用MongoDB时,在创建索引会涉及到在复制集(replication)以及分片(Shard)中创建,为了最大限度地减少构建索引的影响,在副本...

ccww_
27分钟前
18
0
SAP HANA数据库multi container模式JDBC链接connection refused

报错如下信息 com.sap.db.jdbc.exceptions.JDBCDriverException: SAP DBTech JDBC: Cannot connect to jdbc:sap://xxx.xxx.xxx.xxx:30015 [Cannot connect to host xxx.xxx.xxx.xxx:30015 [C......

flash胜龙
52分钟前
37
0
c++ 虚基类

c++ 虚基类 p556

天王盖地虎626
59分钟前
93
0
k8s删除Terminating状态的命名空间

背景: 我们都知道在k8s中namespace有两种常见的状态,即Active和Terminating状态,其中后者一般会比较少见,只有当对应的命名空间下还存在运行的资源,但是该命名空间被删除时才会出现所谓的...

Andy-xu
今天
85
0
seata源码阅读笔记

seata源码阅读笔记 本文没有seata的使用方法,怎么使用seata可以参考官方示例,详细的很。 本文基于v0.8.0版本,本文没贴代码。 seata中的三个重要部分: TC:事务协调器,维护全局事务和分支...

东都大狼狗
今天
48
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部