1. 问题定义
最长不重复子串：一个字符串中最长的没有重复字符的子串。
举个🌰 :
-
abcabcbb最长子串abc长度为3 -
bbbbbbb最长子串b长度为1 -
abdevbac最长子串devbac长度为6
2. 暴力破解:
对于最长不重复子串问题，最粗暴的办法是: 找到所有字符串的子串，遍历每一个子串，判断它们是否是不重复的，然后从中选出最长的不重复子串。一个子串由子串的起点和终点确定，因此对于一个长度为n的字符串，共有n^2个子串。这些子串的平均长度大约为n/2,因此这种解法的时间复杂度是O(n^3);
解法:
string lengthOfLongestSubstring (string &s){
if (s.empty()) {
return "";
}
if (s.size() == 1) {
return s;
}
// 字符串 长度
unsigned long length = s.size();
// 最长 无重复 字符串 长度
int maxLength = 0;
// 最长 无重复 字符串 起始地址
int start = 0;
// 外面 两层 循环 主要 遍历 每一个 子串
for (int i = 0; i < length; i++) {
for (int j = i+1; j < length; j++) {
bool isRepeat = false;
// 判断 该 字符 在 之前 子串中 是否 存在
for (int k = i; k < j; k++) {
if (s.at(k) == s.at(j)) {
isRepeat = true;
break;
}
}
// 如果 存储 跳出 循环 遍历 下一个 字符
if (isRepeat == true) {
break;
}
// 如果 不存在 判断 并 更新
else if(j - i > maxLength){
maxLength = j - i;
start = i;
}
}
}
return s.substr(start, maxLength+1);
}
3. hash实现
hash实现: 两次循环得到所有的子串，通过hash值来判断是否重复。
- 以字符对应的
ASCII码作为hash值，利用数组指针visit来存储，当visit[s.at(i)] == 0, 说明这个字符还没有出现过，如果visit[s.at(j)] == 1,说明该字符出现过。 - 再每次内层循环开始的时候，都要将
visit指向的数组初始化为0，每次内层循环求的是s[i....j]之间的子串，遍历i—j的每个字符，如果字符i之前没出现过，将该字符的visit[s.at(i)] 置为1，继续遍历下个字符，如果该字符出现过，判断是否需要更新，并跳出循环。
解法:
string lengthOfLongestSubstring2 (string &s){
if (s.empty()) {
return "";
}
if (s.size() == 1) {
return s;
}
// 字符串 长度
unsigned long length = s.size();
// 最长 无重复 字符串 长度
int maxLength = 0;
// 最长 无重复 字符串 起始地址
int start = 0;
int *visit = new int[256]();
for (int i = 0; i < length; i++) {
memset(visit, 0x00, sizeof(int[256]));
// 该 字符 未 出现 过
visit[s.at(i)] = 1;
for (int j = i + 1; j < length; j++) {
// 该 字符 未 出现 过
if (visit[s.at(j)] == 0) {
visit[s.at(j)] = 1;
}
// 该字符 出现 过
else {
if (j - i > maxLength) {
maxLength = j - i;
start = i;
}
break;
}
}
}
free(visit);
return s.substr(start, maxLength);
}
C语言方法:
// 最长 不重复 子串(hash方法)
int lengthOfLongestNoRepeatSubstringOne(char *string, int length) {
if (string == NULL) {
return 0;
}
if (length == 1) {
return 1;
}
int maxSubStringLength = 1;
int visitCharArray[256] = {0};
for (int tmpFirstIndex = 0; tmpFirstIndex < length; tmpFirstIndex++) {
visitCharArray[string[tmpFirstIndex]] = 1;
for (int tmpSecondIndex = tmpFirstIndex + 1; tmpSecondIndex < length; tmpSecondIndex++) {
// 该字符 没有 出现过
if (visitCharArray[string[tmpSecondIndex]] == 0) {
visitCharArray[string[tmpSecondIndex]] = 1;
}
else {
if (tmpSecondIndex - tmpFirstIndex > maxSubStringLength) {
maxSubStringLength = tmpSecondIndex - tmpFirstIndex;
}
break;
}
}
}
return maxSubStringLength;
}
4. 动态规划 + hash
举个🌰 :
对于字符串"axbdebpqawuva",构造下表:
image.png
-
表中该字符串有
3个a，有2个b,其余为单一字符。 -
next[]记录了下一个与之重复的字符位置，如str[0] = str[8] = str[12] = 'a',这是next[0] = 8,next[8] = 12,next[12] = 13; 其余同理。 -
值得注意的是，对于没有重复字符的，
next[]存储字符结束符下标'\0',即13。 -
first[i]表示i之后，第一次出现重复字符的位置，例如，str[0]之后，第一次出现重复字符是str[5] = 'b',当然从str[1],str[2]开始也是一样。而从str[3]开始，要到str[12]才出现重复字符'a'。可以证明，从str[i]的最长符合要求的长度为first[i]-i,区间为[i, first[i]-1]由此得解。上述最长串是i = 3时，first[i] - i = 12 - 3 = 9。结果串为debpqawuv。
解法:
string lengthOfLongestSubstring4 (string &s){
if (s.empty()) {
return "";
}
if (s.size() == 1) {
return s;
}
// 字符串 长度
int length = (int)s.size();
// 最长 无重复 字符串 长度
int maxLength = 0;
// 最长 无重复 字符串 起始地址
int start = 0;
// next[i]记录下一个与str[i]重复字符的位置
int *next = new int[length];
memset(next, 0, sizeof(int) * length);
// first[i]记录str[i]后面最近一个重复点
int *first = new int[length+1];
memset(first, 0, sizeof(int) * (length + 1));
int *visit = new int[256];
first[length] = length;
memset(visit, length, sizeof(int) * 256);
// 倒叙 遍历 是为了计算 first和next的值
for (int i = length - 1 ; i >= 0; i--) {
next[i] = visit[s[i]];
visit[s.at(i)] = i;
// 该 字符 出现 过
if (next[i] < first[i+1]) {
first[i] = next[i];
}
// 该 字符 未出现 过
else {
first[i] = first[i+1];
}
}
for (int i = 0; i < length; i++) {
if (first[i] - i > maxLength) {
maxLength = first[i] - i;
start = i;
}
}
free(first);
free(next);
cout<<s.substr(start, maxLength)<<endl;
return s.substr(start, maxLength);
}
从代码和分析中我们可以看出，最长的无重复子串只跟first[i]数组有关，而next[i]只是作为中间变量，临时存储visit[s[i]]的值，因此next[i]可以直接用变量来代理。
解法:
string lengthOfLongestSubstring4 (string &s){
if (s.empty()) {
return "";
}
if (s.size() == 1) {
return s;
}
// 字符串 长度
int length = (int)s.size();
// 最长 无重复 字符串 长度
int maxLength = 0;
// 最长 无重复 字符串 起始地址
int start = 0;
int next = 0;
// first[i]记录str[i]后面最近一个重复点
int *first = new int[length+1];
memset(first, 0, sizeof(int) * (length + 1));
int *visit = new int[256];
first[length] = length;
memset(visit, length, sizeof(int) * 256);
// 倒叙 遍历 是为了计算 first和next的值
for (int i = length - 1 ; i >= 0; i--) {
next = visit[s[i]];
// 存储 每个 字符的 位置
visit[s.at(i)] = i;
// 该 字符 出现 过
if (next < first[i+1]) {
first[i] = next;
}
// 该 字符 未出现 过
else {
first[i] = first[i+1];
}
}
for (int i = 0; i < length; i++) {
if (first[i] - i > maxLength) {
maxLength = first[i] - i;
start = i;
}
}
free(first);
cout<<s.substr(start, maxLength)<<endl;
return s.substr(start, maxLength);
}
C语言解法:
// 最长 不重复 子串(辅助数组 + hash)
int lengthOfLongestNoRepeatSubstringTwo(char *string, int length) {
if (string == NULL) {
return 0;
}
if (length == 1) {
return 1;
}
int maxSubStringLength = 1;
int visitCharArray[256] = {length};
for (int tmpIndex = 0; tmpIndex < 256; tmpIndex++) {
visitCharArray[tmpIndex] = length;
}
// 重复 数字 索引 下标
int repeatPosition = 0;
// 开辟 存储 重复 字符 的数组
int *positionArray = (int *)malloc((length + 1)*sizeof(int));
for (int tmpIndex = 0; tmpIndex <= length; tmpIndex++) {
positionArray[tmpIndex] = length;
}
for (int tmpIndex = length - 1; tmpIndex >=0; tmpIndex--) {
repeatPosition = visitCharArray[string[tmpIndex]];
// 存储 每个 字符 的位置
visitCharArray[string[tmpIndex]] = tmpIndex;
// 该字符 出现过
if (repeatPosition < positionArray[tmpIndex + 1]) {
positionArray[tmpIndex] = repeatPosition;
}
// 该字符 没出现过
else {
positionArray[tmpIndex] = positionArray[tmpIndex + 1];
}
}
for (int tmpIndex = 0; tmpIndex < length; tmpIndex++) {
if (positionArray[tmpIndex] - tmpIndex > maxSubStringLength) {
maxSubStringLength = positionArray[tmpIndex] - tmpIndex;
}
}
return maxSubStringLength;
}
网友评论