LeetCode 657: Robot Return to Origin

問題描述

There is a robot starting at the position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.

You are given a string moves that represents the move sequence of the robot where moves[i] represents its ith move. Valid moves are 'R' (right), 'L' (left), 'U' (up), and 'D' (down).

Return true if the robot returns to the origin after it finishes all of its moves, or false otherwise.

Note: The way that the robot is facing is irrelevant. 'R' will always make the robot move to the right once, 'L' will always make it move left, etc. Also, assume that the magnitude of the robot’s movement is the same for each move.

限制條件

• 1 <= moves.length <= 2 * 104
• moves only contains the characters 'U', 'D', 'L' and 'R'.

範例

• Example 1:
  Input: moves = "UD"
  Output: true
  Explanation: The robot moves up once, and then down once. All moves have the same magnitude, so it ended up at the origin where it started. Therefore, we return true.
• Example 2:
  Input: moves = "LL"
  Output: false
  Explanation: The robot moves left twice. It ends up two moves to the left of the origin. We return false because it is not at the origin at the end of its moves.

解法一：計數器

解題思路

本題的要求是在經過一連串的移動後，檢查機器人是否會回到原點，因此我們只要確認在 moves 陣列中的所有 'L' 與 'R' 數量相同，且 'U' 與 'D' 的數量也相同即可。

步驟詳解

1. 使用計數器 moves_counter 來統計 moves 中所有元素出現的次數（若不想使用原生的 Counter，也可以使用一般 hash table 來實現）。
2. 若 'U' 出現次數與 'D' 出現次數一樣，且 'L' 出現次數與 'R' 出現次數一樣，回傳 True，否則回傳 False。

程式碼

def judge_circle(moves: str) -> bool:
    moves_counter = Counter(moves)
    return (
        moves_counter.get('U') == moves_counter.get('D') and
        moves_counter.get('L') == moves_counter.get('R')
    )

複雜度分析

• 時間複雜度：O(N)，其中 N 為 moves 的長度。
• 空間複雜度：O(N)，其中 N 為 moves 的長度。

參考資料

• LeetCode 原題出處：Robot Return to Origin – LeetCode