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.
1#include <string.h>
2#include <stdlib.h>
3#include <stdio.h>
4
5#define TABLE_SIZE 10007 // A prime number for hash table size
6
7typedef struct Node {
8 int x, y;
9 struct Node* next;
10} Node;
11
12Node* hash_table[TABLE_SIZE];
13
14unsigned int hash(int x, int y) {
15 return ((unsigned int)((x + 100000) * 31 + (y + 100000))) % TABLE_SIZE;
16}
17
18int insert(int x, int y) {
19 unsigned int h = hash(x, y);
20 Node* node = hash_table[h];
21 while (node) {
22 if (node->x == x && node->y == y) return 1;
23 node = node->next;
24 }
25 Node* new_node = (Node*)malloc(sizeof(Node));
26 new_node->x = x;
27 new_node->y = y;
28 new_node->next = hash_table[h];
29 hash_table[h] = new_node;
30 return 0;
31}
32
33void free_table() {
34 for (int i = 0; i < TABLE_SIZE; ++i) {
35 Node* node = hash_table[i];
36 while (node) {
37 Node* temp = node;
38 node = node->next;
39 free(temp);
40 }
41 }
42}
43
44int isPathCrossing(char* path) {
45 memset(hash_table, 0, sizeof(hash_table));
46 int x = 0, y = 0;
47 insert(x, y);
48 while (*path) {
49 if (*path == 'N') y++;
50 else if (*path == 'S') y--;
51 else if (*path == 'E') x++;
52 else if (*path == 'W') x--;
53
54 if (insert(x, y)) {
55 free_table();
56 return 1;
57 }
58 path++;
59 }
60 free_table();
61 return 0;
62}This C solution employs a manual hash table with chaining to store the visited coordinates, similar conceptually to a set. We define a hash function to map each coordinate to a hash table entry and use linked lists for collision resolution. Starting from (0, 0), we adjust coordinates per path, inserting each into the hash table and checking if it has been visited before.
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.
1function
JavaScript function applies a Set to hold coordinate strings. X and Y adjust by 'N', 'S', 'E', 'W', checking each step, marking visits.