Hash Table
String
Description
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 <= 104
path[i]
is either 'N'
, 'S'
, 'E'
, or 'W'
.
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution :
def isPathCrossing ( self , path : str ) -> bool :
i = j = 0
vis = {( 0 , 0 )}
for c in path :
match c :
case 'N' :
i -= 1
case 'S' :
i += 1
case 'E' :
j += 1
case 'W' :
j -= 1
if ( i , j ) in vis :
return True
vis . add (( i , j ))
return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution {
public boolean isPathCrossing ( String path ) {
int i = 0 , j = 0 ;
Set < Integer > vis = new HashSet <> ();
vis . add ( 0 );
for ( int k = 0 , n = path . length (); k < n ; ++ k ) {
switch ( path . charAt ( k )) {
case 'N' -> -- i ;
case 'S' -> ++ i ;
case 'E' -> ++ j ;
case 'W' -> -- j ;
}
int t = i * 20000 + j ;
if ( ! vis . add ( t )) {
return true ;
}
}
return false ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 class Solution {
public :
bool isPathCrossing ( string path ) {
int i = 0 , j = 0 ;
unordered_set < int > s {{ 0 }};
for ( char & c : path ) {
if ( c == 'N' ) {
-- i ;
} else if ( c == 'S' ) {
++ i ;
} else if ( c == 'E' ) {
++ j ;
} else {
-- j ;
}
int t = i * 20000 + j ;
if ( s . count ( t )) {
return true ;
}
s . insert ( t );
}
return false ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 func isPathCrossing ( path string ) bool {
i , j := 0 , 0
vis := map [ int ] bool { 0 : true }
for _ , c := range path {
switch c {
case 'N' :
i --
case 'S' :
i ++
case 'E' :
j ++
case 'W' :
j --
}
if vis [ i * 20000 + j ] {
return true
}
vis [ i * 20000 + j ] = true
}
return false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 function isPathCrossing ( path : string ) : boolean {
let [ i , j ] = [ 0 , 0 ];
const vis : Set < number > = new Set ();
vis . add ( 0 );
for ( const c of path ) {
if ( c === 'N' ) {
-- i ;
} else if ( c === 'S' ) {
++ i ;
} else if ( c === 'E' ) {
++ j ;
} else if ( c === 'W' ) {
-- j ;
}
const t = i * 20000 + j ;
if ( vis . has ( t )) {
return true ;
}
vis . add ( t );
}
return false ;
}
GitHub