818. Race Car

Your car starts at position 0 and speed +1 on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions ‘A’ (accelerate) and ‘R’ (reverse):

• When you get an instruction ‘A’, your car does the following:

  • position += speed
  • speed *= 2

• When you get an instruction ‘R’, your car does the following:

  • If your speed is positive then speed = -1
  • otherwise speed = 1

Your position stays the same.
For example, after commands “AAR”, your car goes to positions 0 —> 1 —> 3 —> 3, and your speed goes to 1 —> 2 —> 4 —> -1.

Given a target position target, return the length of the shortest sequence of instructions to get there.

• Time : O(n)
• Space : O(n)

c++

class Solution {
    int makeKey(int pos, int speed) {
        return speed * 10000 + (speed < 0 ? -pos : pos);
    }
public:
    int racecar(int target) {
        queue<pair<int, int>> q;
        unordered_set<int> visit;
        q.push({0,1});
        visit.insert(makeKey(0,1));
        for(int level = 1; !q.empty(); level++) {
            int sz = q.size();
            while(sz--) {
                auto [position, speed] = q.front(); q.pop();
                int reverseKey = makeKey(position, speed > 0 ? -1 : 1);
                if(!visit.count(reverseKey)) {
                    visit.insert(reverseKey);
                    q.push({position, speed > 0 ? -1 : 1});
                }
                int nextPosition = position + speed, nextSpeed = speed*2;
                int nextKey = makeKey(nextPosition, nextSpeed);
                if(!visit.count(nextKey) and 0 < nextPosition and nextPosition < target * 2) {
                    if(nextPosition == target) return level;
                    visit.insert(nextKey);
                    q.push({nextPosition, nextSpeed});
                }
            }
        }
        return -1;
    }
};