ゼロから始めるLeetCode Day71 「1496. Path Crossing」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day70 「295. Find Median from Data Stream」

次回
ゼロから始めるLeetCode Day72 「1498. Number of Subsequences That Satisfy the Given Sum Condition」

Twitterやってます。

問題

1496. Path Crossing

難易度はEasy。
一番新しく追加されたEasyの問題です。

問題としては、path[i] = ‘N’, ‘S’, ‘E’, ‘W’ のような文字列のパスが与えられたとき，それぞれ1単位の移動を表す．2 次元平面上の原点 (0, 0) を起点とし、path で指定されたパス上を歩きます。
パスが任意の点で交差している場合、つまり以前に訪れたことのある場所にいる場合はTrueを返します。それ以外の場合は False を返します。

画像の関係で例を貼れないので各自確認をよろしくお願いいたします。

解法

x,yで座標を管理して最初の座標をdictで管理する、という方法を取りました。
うーん。
あまりスマートではないと思うのですが、pathをfor文で回して各文字列と一致するならば座標を変更するというものです。
しかしこれでも回答数が少ないせいかスピード自体は上位なんですよね・・・
何とも言えませんがとりあえず今回はこれで。

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        x = y = 0
        isVisited = {(0,0):True}
        for i in path:
            if i == 'N':
                y += 1
            elif i == 'E':
                x += 1
            elif i == 'S':
                y -= 1
            else:
                x -= 1
            if isVisited.get((x,y)):
                return True
            isVisited[(x,y)] = True
        return False
# Runtime: 24 ms, faster than 96.92% of Python3 online submissions for Path Crossing.
# Memory Usage: 14 MB, less than 100.00% of Python3 online submissions for Path Crossing.

Javaとかだとswitch文とかで書くのがいいのでしょうか・・・？
今回は新しい問題という事でdiscussにも投稿してみました。
Simple Python Solution

緊張しますがこういうのやるともっと頭の良い人からアドバイスがもらえたりしていいですよね！

では今回はここまで。お疲れ様でした。