1496. 判断路径是否相交

🟢   🔖  哈希表 字符串  🔗 力扣 LeetCode

题目

Given a string path, where path[i] = 'N', 'S', 'E' or 'W', each representing moving one unit north, south, east, or west, respectively. You start at the origin (0, 0) on a 2D plane and walk on the path specified by path.

Return true if the path crosses itself at any point, that is, if at any time you are on a location you have previously visited. Return false otherwise.

Example 1:


Input: path = "NES"

Output: false

Explanation: Notice that the path doesn't cross any point more than once.

Example 2:


Input: path = "NESWW"

Output: true

Explanation: Notice that the path visits the origin twice.

Constraints:

• 1 <= path.length <= 10^4
• path[i] is either 'N', 'S', 'E', or 'W'.

题目大意

给你一个字符串 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[i] 为 'N'、'S'、'E' 或 'W'

解题思路

可以通过记录已经访问过的坐标来判断是否会与之前的路径相交。

1. 使用 (x, y) 坐标表示当前位置，初始化为 (0, 0)。
2. 用一个 Set 保存已经访问过的坐标。初始状态加入 0,0。
3. 遍历路径字符串 path，根据字符 N/S/E/W 更新 (x, y) 的值：
   • N: y++
   • S: y--
   • E: x++
   • W: x--
4. 将当前坐标序列化为字符串，例如 "x,y"。
   • 如果 Set 中已经存在该坐标，说明路径相交，返回 true。
   • 否则将该坐标加入 Set。
5. 遍历完成后，若没有发现重复坐标，返回 false。

复杂度分析

• 时间复杂度: O(n)，遍历路径字符串一次。
• 空间复杂度: O(n)，最多需要记录路径中所有坐标。

代码

/**
 * @param {string} path
 * @return {boolean}
 */
var isPathCrossing = function (path) {
	let x = 0,
		y = 0;
	let visited = new Set();
	visited.add('0,0');
	for (let move of path) {
		if (move == 'N') {
			y++;
		} else if (move == 'S') {
			y--;
		} else if (move == 'E') {
			x++;
		} else if (move == 'W') {
			x--;
		}
		const location = `${x},${y}`;
		if (visited.has(location)) return true;
		visited.add(location);
	}
	return false;
};