LeetCode 5448. 判斷路徑是否相交(195周賽)

題目

給你一個字元串 

path

，其中 

path[i]

 的值可以是 

'N'

、

'S'

'E'

 或者 

'W'

，分别表示向北、向南、向東、向西移動一個機關。

機器人從二維平面上的原點 

(0, 0)

 處開始出發，按 

path

 所訓示的路徑行走。

如果路徑在任何位置上出現相交的情況，也就是走到之前已經走過的位置，請傳回 

True

 ；否則，傳回 

False

 。

示例 1：

輸入：path = "NES"

輸出：false

解釋：該路徑沒有在任何位置相交。

示例 2：

輸入：path = "NESWW"

輸出：true

解釋：該路徑經過原點兩次。

提示：

• 1 <= path.length <= 10^4

• path

   僅由 

  {'N', 'S', 'E', 'W}

   中的字元組成

解題思路

用數組記錄曾經走過的路徑

def isPathCrossing(self, path: str) -> bool:
        pathList = list(path)
        stepList = ["0 0"]
        while len(pathList)>0:
            # print(stepList)
            step = pathList.pop(0)
            lastStep = stepList[-1]
            tempList = lastStep.split(" ")
            x = int(tempList[0])
            y = int(tempList[1])
            if step == "N":
                y = y +1
            elif step == "S":
                y = y - 1
            elif step == "E":
                x = x + 1
            elif step == "W":
                x = x - 1
            newStepStr = str(x) + " " + str(y)
            if newStepStr in stepList:
                return True
            stepList.append(newStepStr)
        return False