始めに
LeetCodeで解いた問題をアウトプットしてさらに理解を深めていく目的で投稿してます。
解説が間違っていたり、さらに良い解法などあればバシバシご指摘お願いします
それでは行ってみよう
問題
タイトルにもあるが今回はSimplify Pathという問題を解いていく
Unix系の絶対パスを簡略化するアルゴリズムを組む。
難易度はmediumなのである程度の考察力が必要になる。
とは言えmediumの中でもそれほど難易度は高くない気もするので人によってはすんなり解けるかも？
ちなみに私は回答に40分近くかかり、実際のコーディング面接等ではかなり厳しいように感じたのでまだまだレベル上げが必要。
問題の考察
まずこの問題を解く上で必要な考察としてスタックを使って解こうとと思った人は勘が鋭い。
前に適切な括弧の判定という問題をやったので、これって前にやった問題に似てる？
と思い、スタックを使うという考えに至った。
正直、この手の問題をやったことない状態でいきなりスタックを使おうと思う人はかなりセンスがあると思う。少なくとも自分は無理
他に考慮すべき点は以下となる
- どんな文字をスタックに追加すればいいのか？
- どんな時にスタックから削除すれば良いのか？
ではまず、どんな文字をスタックに追加するか？ ですが
/home//foo/
上記を例にするとhome,foo(ディレクトリ)の部分をスタックに追加してあげよう。
続いてどんな時にスタックから削除するのか？
これは「..」が来た際は直前のディレクトリは省略が可能なのでpopができる。
/home/foo/../
↓ fooが省略
/home
解法
前準備
省略したディレクトリを入れるstackを用意し、split関数を使い「/」区切りでsegmentsに代入
path = "/a/b/c/../../d/"
segments = ['', 'a', 'b', 'c', '..', '..', 'd', '']
/区切りにするとsegmentsは上記のようになる。
def simplifyPath(self, path: str) -> str:
stack = []
segments = path.split("/")
segmentsをループし、適切な処理をする。
考察パートで話したどんな時にスタックから削除すれば良いのか？
これは以下の条件で達成できる
# 既にstack内にディレクトリが含まれる かつ 「..」が含まれる場合
if stack and segment == "..":
stack.pop()
次にどんな文字をスタックに追加すればいいのか？
segments = ['', 'a', 'b', 'c', '..', '..', 'd', '']の 場合、
a,b,c,dがstackに追加される。
要はディレクトリ部分をstackに追加していけば良い。
elif segment not in [".", "", ".."]:
stack.append(segment)
最後にstackを「/」で連結していけばOK
このコードの計算量はO(N)です。
以下はコード全体です
def simplifyPath(self, path: str) -> str:
# 前処理は省略
for segment in segments:
if stack and segment == "..":
stack.pop()
elif segment not in [".", "", ".."]:
stack.append(segment)
return "/" + "/".join(stack)
これまでのまとめ
これまでの処理をまとめると以下のようになる
- 絶対パスを/区切りでstackで管理
- homeやfooなどのディレクトリはstackに追加していく
- 「..」など一階層上を指す場合、1つ上の階層を削除(stackをpopする)
- 最後はstackを/で連結すれば完了
感想
やっぱりEasyと比べると難易度は高い...
当面の目標はMediumが問題なく解けるレベル感まで持っていく必要がありそう。
まだまだ道のりは長い