3. Longest Substring Without Repeating Characters
题目要求
给定一个字符串，找到一个子字符串最长且没有重复字符
样例
1 | Example 1: |
解决方式
以下为我个人的解决方式，可能并不是最优解，该博客仅作为思考记录
穷举法
这是最容易想到的一种解决方式，截取出所有的字串。并将所有的字串遍历一遍，过滤有重复字符的字串，取最长的。
当然这时最低效的方法，我提交了之后直接超时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
33
34
35use std::collections::HashSet;
impl Solution {
pub fn length_of_longest_substring(s: String) -> i32 {
let result = Solution::all_sub_str(&s);
if result.len() == 0 {
return 0;
}
let mut most_len = 0;
for str in result {
if Solution::widthout_repit_str(str) && str.len() > most_len {
most_len = str.len();
}
}
// println!("{:?} {:?}", result, &s[0..7]);
return most_len as i32;
}
pub fn all_sub_str<'a>(s:&'a str) -> Vec<&'a str> {
let mut strs = Vec::new();
for i in 0..s.len() {
for j in i+1..s.len() + 1 {
strs.push(&s[i..j]);
}
}
return strs;
}
pub fn widthout_repit_str(s : &str) -> bool {
let mut char_set = HashSet::new();
for s_char in s.chars() {
char_set.insert(s_char);
}
char_set.len() == s.len()
}
}
使用滑动窗口解决
V1
因为需要解决的问题是找到连续的且无重复字符的最长字串
所以使用两个变量存储左右指引位置1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24use std::cmp::max;
impl Solution {
pub fn length_of_longest_substring(s: String) -> i32 {
let mut str_chars = [0;128];
let mut left = 0;
let mut right = 0;
let mut result= 0;
while right < s.len() {
let right_char_in_str = s.chars().nth(right).unwrap();
let right_char_index = right_char_in_str as usize;
str_chars[right_char_index] = str_chars[right_char_index] + 1;
while str_chars[right_char_index] > 1 {
let left_char_in_str = s.chars().nth(left).unwrap();
let left_char_index = left_char_in_str as usize;
str_chars[left_char_index] = str_chars[left_char_index] - 1;
left = left + 1;
}
right = right + 1;
result = max(right - left, result);
}
result as i32
}
}
但第一个版本 耗时还是太长了,并没有通过测试，在想是不是在字符索引的时候耗时过多
所以进入前先将字符串变为字符数组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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49use std::cmp::max;
impl Solution {
pub fn length_of_longest_substring(s: String) -> i32 {
let mut str_chars = [0;128];
let mut left = 0;
let mut right = 0;
let mut result= 0;
while right < s.len() {
let right_char_in_str = s.chars().nth(right).unwrap();
let right_char_index = right_char_in_str as usize;
str_chars[right_char_index] = str_chars[right_char_index] + 1;
while str_chars[right_char_index] > 1 {
let left_char_in_str = s.chars().nth(left).unwrap();
let left_char_index = left_char_in_str as usize;
str_chars[left_char_index] = str_chars[left_char_index] - 1;
left = left + 1;
}
right = right + 1;
result = max(right - left, result);
}
result as i32
}
}
// 再次优化索引
use std::cmp::max;
impl Solution {
pub fn length_of_longest_substring(s: String) -> i32 {
let mut str_chars = [0;128];
let mut left = 0;
let mut right = 0;
let mut result= 0;
let s_bytes = s.as_bytes();
for &right_char in s_bytes {
let right_char_index = right_char as usize;
str_chars[right_char_index] = str_chars[right_char_index] + 1;
while str_chars[right_char_index] > 1 {
let left_char_index = s_bytes[left] as usize;
str_chars[left_char_index] = str_chars[left_char_index] - 1;
left = left + 1;
}
right = right + 1;
result = max(right - left, result);
}
result as i32
}
}
V2
后面想到,是不是在进行右指针滑动时,同时更新左指针.
假如右指针滑动到已经存在的字符时,那么左指针已经不可能出现在低于当前重复字符前一个索引位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
30impl Solution {
pub fn length_of_longest_substring(s: String) -> i32 {
let mut str_chars = [0;128];
let mut left = 0;
let mut result= 0;
for (right, ch) in s.char_indices() {
left = str_chars[ch as usize].max(left);
str_chars[ch as usize] = right + 1;
result = result.max(str_chars[ch as usize] - left);
}
result as i32
}
}
// 优化循环方式
impl Solution {
pub fn length_of_longest_substring(s: String) -> i32 {
let mut str_chars = [0;127];
let mut left = 0;
let mut result= 0;
for (right, ch) in s.char_indices().map(|(i, c)| (i as u32, c as usize)) {
left = str_chars[ch].max(left);
str_chars[ch] = right + 1;
result = result.max(str_chars[ch] - left);
}
result as i32
}
}