[LeetCode] 071. Simplify Path

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

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
path = "/a/../../b/../c//.//", => "/c"
path = "/a//b////c/d//././/..", => "/a/b/c"

In a UNIX-style file system, a period (’.’) refers to the current directory, so it can be ignored in a simplified path. Additionally, a double period ("…") moves up a directory, so it cancels out whatever the last directory was. For more information, look here: https://en.wikipedia.org/wiki/Path_(computing)#Unix_style


Corner Cases:

  • Did you consider the case where path= "/../"?
    In this case, you should return "/".
  • Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
    In this case, you should ignore redundant slashes and return "/home/foo".


解題邏輯與實作

這題是要將給定的路徑進行簡化,路徑中可能會出現的元素有三種分別是...及folder或file(先假裝他們是吧,不然我也不知道怎麼稱呼他們XD)

如果熟悉Unix的路徑規則的話,應該會認的這幾個符號,我用自己的想法稍微做個歸納,不過路徑規則不熟的話好像也沒關係,花點時間找一下題目規律而已:

  1. .:表示,同一層目錄,可以直接跳過不參考
  2. ..:表示返回上一層,所以應該取消(刪除)上一個的路徑指令,另外根據Corner Cases給的提示,若上一層超過所給定的路徑,直接回傳 ‘/’

另外需要處理的就是正規化左斜線,去除冗餘的斜線。


Stack

這題可以使用stack來實做,依照上面的解題邏輯:遇到.就跳過、..就pop,若非以上兩者就push進stack,整題實做流程如下:

  1. 使用regular expression,先將路徑正規化
  2. 將路徑依左斜線切斷後,依序取出
    1. 若為.,就跳過不執行
    2. 若為..就,且stack不為空,就pop最頂層元素
    3. 若非以上兩者,就當作是一個folder或file,將他push進入stack
  3. 最後將stack中的結果使用左斜線串接起來



程式碼

import re
class Solution:
	def preprocess(self,path):
		reg = r'/+'
		path = re.sub(reg, "/", path)
		path = path.strip('/')
		return path.split("/")

	def simplifyPath(self, path):
		stack = []
		tokens = self.preprocess(path)

		for t in tokens:
			if t == '.':
				continue
			elif t == '..':
				if len(stack) > 0:
					stack.pop()
			else :
				stack.append(t)

		return "/"+"/".join(stack)

不過跑出來的效能有點不盡理想,只有 96 ms, 2.95% 。

所以稍微Tune了一下,放棄使用regular expression做正規化了,改成直接使用左斜線切斷後,若是遇到需要正規化的部份,切斷後的結果會是空字串,此時跳過不處理,就可以達到對左斜線做正規化的效果了


程式碼

class Solution:
	def simplifyPath(self, path):
		stack = []
		tokens = path.split("/")
		for t in tokens:
			if len(t) == 0 or t == '.':
				continue
			elif t == '..':
				stack = stack[:-1]
			else :
				stack.append(t)

		return "/"+"/".join(stack)

跑出來的效能果然進步許多,52 ms, 49.56% ,雖然還是沒有過半…



[LeetCode] 解題目錄 -> 這裡走

留言

這個網誌中的熱門文章

Genymotion 模擬器安裝篇:In ubuntu14.04 LET