How do I solve the Robot Return to Origin problem?

You can solve this problem by counting the occurrences of each move and checking if the horizontal and vertical movements cancel out.

What is the time complexity of the Robot Return to Origin solution?

The time complexity is O(N), where N is the length of the move sequence, because we need to process each move once.

How can I optimize the solution for large inputs in Robot Return to Origin?

The solution is already optimized with O(N) time and O(1) space complexity. You can further optimize by using a constant number of variables for tracking position.

Can you handle edge cases for Robot Return to Origin?

Yes, ensure to handle edge cases like a single move or a move sequence that doesn't cancel out, resulting in a false output.

What patterns are involved in solving the Robot Return to Origin?

This problem involves string manipulation and simulation to track the robot's position and validate if it returns to the origin.

#657

Easy

auto_awesomestring·结合·模拟

LeetCode 题解工作台

机器人能否返回原点

在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。移动顺序由字符串 moves 表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R （右）， L （左）， U （上）和 D （下）。如果机器人在…

字符串模拟

题目描述

在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。

移动顺序由字符串 moves 表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。

如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。

注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。

示例 1:

输入: moves = "UD"
输出: true
解释：机器人向上移动一次，然后向下移动一次。所有动作都具有相同的幅度，因此它最终回到它开始的原点。因此，我们返回 true。

示例 2:

输入: moves = "LL"
输出: false
解释：机器人向左移动两次。它最终位于原点的左侧，距原点有两次 “移动” 的距离。我们返回 false，因为它在移动结束时没有返回原点。

提示:

1 <= moves.length <= 2 * 10⁴
moves 只包含字符 'U', 'D', 'L' 和 'R'

lightbulb

解题思路

方法一：维护坐标

我们可以维护一个坐标 $(x, y)$ ，分别表示机器人在水平方向和竖直方向上的移动。

遍历字符串 $\textit{moves}$ ，根据当前字符的不同，更新坐标 $(x, y)$ ：

如果当前字符是 'U'，则 $y$ 加 $1$ ；
如果当前字符是 'D'，则 $y$ 减 $1$ ；
如果当前字符是 'L'，则 $x$ 减 $1$ ；
如果当前字符是 'R'，则 $x$ 加 $1$ 。

最后，判断 $x$ 和 $y$ 是否都为 $0$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $\textit{moves}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        x = y = 0
        for c in moves:
            match c:
                case "U":
                    y += 1
                case "D":
                    y -= 1
                case "L":
                    x -= 1
                case "R":
                    x += 1
        return x == 0 and y == 0

speed

复杂度分析

指标	值
时间	O(N)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Assessing the candidate's ability to leverage string manipulations and simulation to solve problems.
question_mark
Evaluating understanding of time and space complexities for simple movement-based problems.
question_mark
Looking for the candidate's approach to validating edge cases like short or long strings.

warning

常见陷阱

外企场景

error
Not considering edge cases such as the smallest and largest strings.
error
Forgetting to check both horizontal and vertical moves when validating the return to origin.
error
Using unnecessary additional data structures or overcomplicating the solution with extra logic.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the plane size and test if the robot still returns to the origin.
arrow_right_alt
Consider diagonal moves or moves that repeat multiple times.
arrow_right_alt
Optimize for cases with very large strings, keeping performance in mind.

help

常见问题

外企场景

继续练习

#640 求解方程 #592 分数加减运算 #537 复数乘法