Write a function dirReduc that takes an array of strings and returns a string array. The returned array should have all unnecessary directions removed, where adjacent opposite directions cancel each other out (NORTH <-> SOUTH and EAST <-> WEST).
Example 1:
Input: ["NORTH", "SOUTH", "EAST", "WEST"]
Output: []Example 2:
Input: ["NORTH", "EAST", "WEST", "SOUTH", "WEST", "WEST"]
Output: ["WEST", "WEST"]Note: Not every path can be reduced. For example, [“NORTH”, “WEST”, “SOUTH”, “EAST”] cannot be fully reduced because the remaining directions are not adjacent opposites.
This problem is a classic stack-based reduction task. Traverse the direction list in order, and whenever the current direction is the opposite of the stack top, pop the stack; otherwise push the current direction. This repeatedly removes adjacent NORTH/SOUTH and EAST/WEST pairs until no more cancellations are possible. The key point is that only adjacent opposites can be removed, so a stack is the right data structure, with O(n) time complexity.
