Path Crossing Leetcode Solution

Problem Statement

In path crossing problem a_string is given in which there are only four different characters 'N', 'S', 'E' or 'W' showing the movement of an object in one direction at a time by 1 unit. Object is initially at origin (0,0). We have to find out if the object will cross its path at any point walking along the path specified in the given string.

Example

path = "NES"

false

Explanation:

 

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

path = "NESWW"

true

Explanation:

 

Notice that the path visits the origin twice.

Approach

From the problem statement it is clear that if a coordinate (x,y) occurs in the path of the object, then it must be the position of the object after certain number of moves as it is moving with 1 unit each time.

So if a point comes in its path which is once previously visited, then it is surely crossing the path. So we can return true as soon as we found this kind of point.

 

Now how do we know that a point has been visited previously. For this we can use a Hash Set and keep storing all the points in its path. At any time if we found that the next point to which object is going is already present in the set, we return true. After completing the path if this doesn't happens, then we return false.

Algorithm :

 

- Create a hash set of keys, where key represents coordinate (x,y). For this we can use pair as key Or we can use a simple string that should represent two integers uniquely.

 

www.tutorialcup.com/leetcode-solutions/path-crossing-leet...

Done