Path Crossing

class Solution {
public:
    bool doesPathCross(string path) {
        unordered_map<char, pair<int, int>> directives;
        directives['N'] = {0, 1};
        directives['S'] = {0, -1};
        directives['W'] = {-1, 0};
        directives['E'] = {1, 0};
            
        unordered_set<string> coordinatesSeen;
        coordinatesSeen.insert("0,0");
            
        int posX = 0;
        int posY = 0;
            
        for (char dir : path) {
            pair<int, int> move = directives[dir];
            int delta_x = move.first;
            int delta_y = move.second;
            posX += delta_x;
            posY += delta_y;
                
            string coordinate = to_string(posX) + "," + to_string(posY);
            if (coordinatesSeen.find(coordinate) != coordinatesSeen.end()) {
                return true;
            }
                
            coordinatesSeen.insert(coordinate);
        }
            
        return false;
    }
};

The provided C++ solution checks if a path defined by a string of directions crosses itself at any point. The solution utilizes an unordered set to track seen coordinates and an unordered map for direction movements.

• The directions 'N', 'S', 'E', 'W' are mapped in the directives unordered map to their respective X and Y coordinate changes.
• Initializes starting position at (0,0) and inserts this starting point into coordinatesSeen.
• Iterate through each character in the path string:
  • Retrieve the respective coordinate movement from the directives map and update the current position.
  • Convert the new position to a string format "x,y" and check if this coordinate is already in the set coordinatesSeen.
  • If found, return true indicating the path crosses.
  • Otherwise, add the new coordinate to the set.
• If the loop concludes without finding any repeated coordinates, return false.

This solution efficiently determines the path crossing by checking and inserting coordinates in O(1) average time due to the unordered set. This results in an overall time complexity of O(n), where n is the length of the path string. The use of the unordered map for constant retrieval of directional movements also contributes to the efficiency of the solution.

class Solution {
    public boolean pathIntersects(String route) {
        Map<Character, Pair<Integer, Integer>> directions = new HashMap();
        directions.put('N', new Pair(0, 1));
        directions.put('S', new Pair(0, -1));
        directions.put('E', new Pair(1, 0));
        directions.put('W', new Pair(-1, 0));
    
        Set<Pair<Integer, Integer>> seenPositions = new HashSet();
        seenPositions.add(new Pair(0, 0));
    
        int posX = 0;
        int posY = 0;
    
        for (char step : route.toCharArray()) {
            Pair<Integer, Integer> move = directions.get(step);
            posX += move.getKey();
            posY += move.getValue();
    
            Pair<Integer, Integer> currentPosition = new Pair(posX, posY);
            if (seenPositions.contains(currentPosition)) {
                return true;
            }
    
            seenPositions.add(currentPosition);
        }
    
        return false;
    }
}

The provided solution in Java addresses the problem of determining if a path crosses itself based on a given sequence of moves. The function pathIntersects uses a hash map directions to associate characters representing directions ('N', 'S', 'E', 'W') with movements in a Cartesian coordinate system. The positions are tracked with a set seenPositions to efficiently check for previously visited coordinates.

• The algorithm initiates by storing the starting point (0, 0) in seenPositions.
• It iterates over each character in the input string route, converting each direction into coordinate changes using the directions map.
• For each move, it adjusts the current position (posX, posY) and checks whether this new position has already been visited. If it has, the function returns true, indicating the path crosses itself.
• If the loop completes without finding any repeated position, it returns false, indicating no crossing.

Key steps in the algorithm:

1. Define a map to translate direction characters to coordinate changes.
2. Initialize a set to track visited positions with the starting position included.
3. Loop through each direction in the route, updating the current position.
4. Check if the new position is already in the visited set. If so, return true.
5. If the loop finishes without finding a crossing, return false.

This approach is efficient due to the use of a hash set allowing for constant time complexity checks on position visits, making the solution optimal for larger routes where multiple moves are involved.

class Solution:
    def pathIntersect(self, route: str) -> bool:
        directions = {
            "N": (0, 1),
            "S": (0, -1),
            "E": (1, 0),
            "W": (-1, 0)
        }
    
        seen = {(0, 0)}
        xpos = 0
        ypos = 0
    
        for move in route:
            move_x, move_y = directions[move]
            xpos += move_x
            ypos += move_y
    
            if (xpos, ypos) in seen:
                return True
    
            seen.add((xpos, ypos))
    
        return False

The provided Python solution addresses the problem of determining if a path crosses itself. The function pathIntersect accepts a string representing a sequence of moves and returns a boolean indicating whether the path crosses at any point. Here’s how the function operates:

• A dictionary named directions maps each move ('N', 'S', 'E', 'W') to a tuple representing the direction in x and y coordinates.
• A set named seen initializes with the starting position (0, 0).
• Two variables, xpos and ypos, track the current position, starting from the origin.
• The function iterates over each move in the input string:
  • It updates the xpos and ypos according to the direction specified in the directions dictionary.
  • Checks if the new position has already been visited by looking it up in the seen set.
  • If the position was seen before, the function returns True, indicating a crossing.
  • Adds the new position to the seen set if no crossing was detected.
• If no crossings are found after processing all moves, the function returns False.