Sponsored
Sponsored
The idea is to use a Set (or a HashSet in some languages) to store each coordinate visited during the path traversal. Starting from (0, 0), each movement updates the coordinates. If the updated coordinates are already in the Set, it means that the path has crossed itself, and we return true. Otherwise, continue until the end of the path and return false.
Time Complexity: O(n), where n is the length of the path, as we iterate through the path once, with O(1) operations for each set lookup.
Space Complexity: O(n), as we store up to n coordinates in the set.
1import java.util.HashSet;
2import java.util.Set;
3
4class Solution {
5 public boolean isPathCrossing(String path) {
6 Set<String> visited = new HashSet<>();
7 int x = 0, y = 0;
8 visited.add(x + "," + y);
9
10 for (char direction : path.toCharArray()) {
11 if (direction == 'N') {
12 y++;
13 } else if (direction == 'S') {
14 y--;
15 } else if (direction == 'E') {
16 x++;
17 } else if (direction == 'W') {
18 x--;
19 }
20
21 String current = x + "," + y;
22 if (visited.contains(current)) {
23 return true;
24 }
25 visited.add(current);
26 }
27 return false;
28 }
29}This Java solution uses a HashSet to store visited coordinates as strings of the form "x,y". Starting at (0, 0), we iterate through the path, updating the coordinates and checking if the current position is already in the set. If it is, the path crosses itself, and we return true; otherwise, we finish by returning false.
In this approach, we simulate movement on a 2D plane. Starting at the origin (0, 0), the path string is processed character by character to update the current position based on the direction: 'N' increases y, 'S' decreases y, 'E' increases x, and 'W' decreases x. A map or set records visits to each unique position. If a position is visited more than once, the path crosses itself.
Time Complexity: O(n), since every character in the path is processed.
Space Complexity: O(n), as we store coordinates in a set.
1using System;
2using System.Collections.Generic;
public class Solution {
public bool IsPathCrossing(string path) {
var visited = new HashSet<(int, int)>();
int x = 0, y = 0;
visited.Add((x, y));
foreach (char direction in path) {
if (direction == 'N') {
y++;
} else if (direction == 'S') {
y--;
} else if (direction == 'E') {
x++;
} else if (direction == 'W') {
x--;
}
var current = (x, y);
if (visited.Contains(current)) {
return true;
}
visited.Add(current);
}
return false;
}
}C# solution leverages a HashSet for tracking coordinates using tuple structures, adjusting position per direction and verifying if any are revisited.