未分類

Simplify Path

Go, LeetCode, Stack, String

Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example:

1
2
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
提示 解題應用
Stack LinkedList
String 規律觀查

Default:

1
2
3
func simplifyPath(path string) string {
}

解答思路:

一開始是將整個路徑以”/“來分割字串，之後就是一一取出陣列中分割完得到的資料夾名稱，並分別對”.”、”..”及其它狀況做處理，最初並沒有想到要用stack來實作儲存，而是直接使用slice的伸縮來取代，如果碰上資料夾名稱則append至slice之中，而如果碰上”..”的情況就直接移除slice的最後一個元素，最後仍可以通過測資，不過用stack的好處就是能使整個邏輯更加好懂，資料夾名稱就新增一個頭節點並將舊的推向後頭，而”..”則直接拿掉頭節點(頭節點移動到下一個)，但不論何種方式碰上”.”就是直接跳過取下一個資料夾名稱，待全數放入slice/stack並處理完後，最後再一口氣遍歷組成新的路徑字串回傳即可。

程式碼解說:

因為stack我是以節點的方式實作，故一開始就要先初始化節點的結構(包含要儲存的資料夾名稱字串與下一個節點的位置)，接著就是將整個路徑以”/“來分割字串，之後一一取出陣列中分割完得到的資料夾名稱，如果碰上”.”或得到的資料夾名稱為空(例://///)就是直接跳過，而如果是”..”且頭節點不為空，則直接拿掉頭節點(頭節點移動到下一個)，至於一般的資料夾名稱就新增一個頭節點並將舊的推向後頭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
type stackNode struct {
	S    string
	Next *stackNode
}
var result string
var top *stackNode
folders := strings.Split(path, "/")
for _, v := range folders {
	if v == "." || v == "" {
		continue
	} else if v == ".." {
		if top != nil {
			top = top.Next
		}
	} else {
		top = &stackNode{v, top}
	}
}

待全數放入stack並處理完後，如果頭節點不為空就遍歷stack節點組回路徑字串(注意遍歷stack取值順序是從路徑的後頭開始)，如果最後的路徑字串長度為0(例:///// 先前因資料夾名稱為空都被跳過)就回傳”/“根目錄，否則就直接回傳路徑字串的結果

1
2
3
4
5
6
7
8
for top != nil {
	result = "/" + top.S + result
	top = top.Next
}
if len(result) == 0 {
	return "/"
}
return result

完整程式碼:

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
type stackNode struct {
	S    string
	Next *stackNode
}
func simplifyPath(path string) string {
	var result string
	var top *stackNode
	folders := strings.Split(path, "/")
	for _, v := range folders {
		if v == "." || v == "" {
			continue
		} else if v == ".." {
			if top != nil {
				top = top.Next
			}
		} else {
			top = &stackNode{v, top}
		}
	}
	for top != nil {
		result = "/" + top.S + result
		top = top.Next
	}
	if len(result) == 0 {
		return "/"
	}
	return result
}

總結:

若給一個Unix路徑字串包含”.”與”..”，要將其做簡化並回傳新的字串，一開始先將整個路徑以”/“來分割字串，之後就是一一取出陣列中分割完得到的資料夾名稱，分別對”.”、”..”及其它狀況做處理，並以stack來儲存新的路徑資料，如果碰上”.”就是直接跳過取下一個資料夾名稱，而”..”則直接拿掉頭節點(頭節點移動到下一個)，至於一般的資料夾名稱就新增一個頭節點並將舊的推向後頭，待全數放入stack並處理完後，最後再一口氣遍歷組成新的路徑字串回傳即可。

分享到