LeetCode算法练习之Longest Substring Without Repeating Characters

题目介绍

Given a string, find the length of the longest substring without repeating characters.
Examples:
Given “abcabcbb”, the answer is “abc”, which the length is 3.
Given “bbbbb”, the answer is “b”, with the length of 1.
Given “pwwkew”, the answer is “wke”, with the length of 3.
Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

—— 题目链接

中文翻译

给定一个字符串,查找长度最长的子串,且该子串没有重复字符。
例如:
当给定的字符串为 “abcabcbb”,最长的子串为 “abc”, 它的长度为3。
当给定的字符串为 “bbbbb”,最长的子串为 “b”, 它的长度为1。
当给定的字符串为 “pwwkew”,最长的子串为 “wke”, 它的长度为3。
注意:返回长度最长的子字符串,必须是给定字符串的子字符串,且必须为连续的。像 “pwke” 就不符合要求,应为它不是子字符串。

解题思路

1.首先,判断给定字符串是否为空,如果是则返回0,否则继续执行程序。
2.先开始截取的字符串从第一个字符开始,也就是下标位置为0,结束位置为k = i + 1
3.判断第k位的字符是否出现在刚才截取的字符串中
4.如果没有,则该字符串长度length+1,k+1,接着判断第k+1位的字符
5.如果有,则终止内部循环,然后比较刚才字符串的长度length与maxLength的值,决定是否赋值
6.截取的字符串的开始位置从第二个字符开始,也就是下标位置为1,结束位置为k = i + 1
7.依次类推,最后返回maxLength的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
//判断字符串是否为空,为空则返回0
if (s) {
//参数i为子字符串开始的位置,k为子字符串结束的位置,length为子字符串的长度,
//maxLength为子字符串最长的长度,初始化为1
var i, k, length, maxLength = 1;
for (i = 0; i < s.length; i++) {
length = 1; //子字符串开始时初始化为1
for (k = i + 1; k < s.length; k++) {
var myString = s.slice(i,k); //截取的子字符串
//判断下标第k位字符是否在子字符串中出现,没有则长度+1
if (myString.indexOf(s.charAt(k)) < 0) {
length++;
} else {
break;
}
}
//判断子字符串的长度是否比maxLength大,如果是则将其赋值给maxLength
maxLength = length > maxLength ? length : maxLength;
}
return maxLength;
}
else{
return 0;
}
};

代码解释

1.ECMAScript提供了三个基于子字符串创建新字符串的方法:slice()、substr()和substring()。这三个方法都会返回被操作字符串的一个子字符串,而且也都接受一或者两个参数。第一个参数指定子字符串开始的位置,第二个人参数(在指定的情况下)表示子字符串到哪里结束。这几个方法用法大同小异,这里用到的是slice(),其他具体细节详见(JavaScript高级程序设计P124)。
2.charAt()与indexOf()是两个相反的方法,charAt()方法以单字符串的形式返回给定位置的那个字符。indexOf()方法则是从一个的字符串中搜索给定的子字符串,然后返回子字符串的位置(如果没有找到则返回-1),与这个方法类似的还有一个lastIndexOf(),lastIndexOf()这个方法则是从字符串的末尾向前搜索子字符串,indexOf()则是从字符串开头向后搜索子字符串。其他具体细节详见(JavaScript高级程序设计P125)。

1
2
3
4
var stringValue = "hello world";
console.log(stringValue.charAt(4))// "o"
console.log(stringValue.indexOf("o"))// "1" 从左向右"o"第一次出现的位置
console.log(stringValue.lastIndexOf("o"))// "7" 从右向左"o"第一次出现的位置

附加内容

总体来说,这个解法思路比较简单,但运行效率真的是不高(只击败了38.58%的解法),故如下贴出LeetCode该题效率比较高的解法,有用到最新ES6语法,有兴趣的可以试着理解!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let m = Array(256).fill(-1), res = 0, left = 0;
for (let i = 0; i < s.length; i++) {
let index = s[i].charCodeAt();
// no duplicates from left -- i
if (m[index] == -1 || m[index] < left) {
res = Math.max(res, i - left + 1);
} else {
// move left to next location of duplicates
left = m[index] + 1;
}
m[index] = i;
}
return res;
};

×

纯属好玩

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

文章目录
  1. 1. 题目介绍
  2. 2. 中文翻译
  3. 3. 解题思路
  4. 4. 代码解释
  5. 5. 附加内容
,