未分類

Longest Substring Without Repeating Characters

Go, HashTable, LeetCode, String, TwoPointers

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

For Examples:

1
2
3
4
5
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.
提示 解題應用
HashTable HashMap
TwoPointers Index位置記錄
String 規律觀查

Default:

1
2
3
func lengthOfLongestSubstring(s string) int {
}

解答思路:

因為需要知道已經出現了哪些字母，所以在一邊遍歷的同時，一邊要將字母儲存至hashmap之中，其中key值為該字母而value則隨意，同時要標註目前所找的長度字串頭與尾的字串位置，在往後遍歷時(標註的尾向往移)如果該字母已經在hashmap之中，此時就不斷將標註的頭往後移，並將原本在頭位置放入hashmap中的值給移除，直到先前尾巴遍歷的值放入hashmap之中不再出現重覆的狀況，此時才能放心的將尾部向後移動，而當尾部順利向後移動時，比較hashmap的大小或尾減去頭的長度與最大值做比較，如果比較大就取代，直到最後遍歷結束後才回傳最大值。

程式碼解說:

一開始先初始化一hashmap，其中key值為該字母而value則隨意(這邊也是放該字母)，接著便開始遍歷字串，如果目前遍歷的值(以rear尾部為主)已存在於hashmap之中，此時就將front頭部位置原本存放在hashmap中的值給移除，移除後才將front向後移動，直到rear遍歷到的值不再出現重覆的狀況，此時才將該值再次放入hashmap之中，並計算hashmap的長度是否大於目前找到最大字串的長度，如果是就取代最大值，直到最後遍歷結束後才回傳最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var max int
var front int
var rear int
var strFront string
var strRear string
hashMap := make(map[string]string)
for rear < len(s) {
	strFront = string(s[front])
	strRear = string(s[rear])
	_, exist := hashMap[strRear]
	if exist {
		delete(hashMap, strFront)
		front++
	} else {
		hashMap[strRear] = strRear
		rear++
		if len(hashMap) > max {
			max = len(hashMap)
		}
	}
}
return max

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func lengthOfLongestSubstring(s string) int {
	var max int
	var front int
	var rear int
	var strFront string
	var strRear string
	hashMap := make(map[string]string)
	for rear < len(s) {
		strFront = string(s[front])
		strRear = string(s[rear])
		_, exist := hashMap[strRear]
		if exist {
			delete(hashMap, strFront)
			front++
		} else {
			hashMap[strRear] = strRear
			rear++
			if len(hashMap) > max {
				max = len(hashMap)
			}
		}
	}
	return max
}

總結:

要從一字串中找出完全不重覆子字串的最大長度，一邊遍歷的同時，一邊要將字母儲存至hashmap之中，其中key值為該字母而value則隨意，同時要標註目前所找的長度字串頭與尾的字串位置，在往後遍歷時(標註的尾向往移)如果該字母已經在hashmap之中，此時就不斷將標註的頭往後移，並將原本在頭位置放入hashmap中的值給移除，直到先前尾巴遍歷的值放入hashmap之中不再出現重覆的狀況，此時才能放心的將尾部向後移動，而當尾部順利向後移動時，比較hashmap的大小或尾減去頭的長度與最大值做比較，如果比較大就取代，直到最後遍歷結束後才回傳最大值。

分享到