Проверить, является ли заданная последовательность ходов круговой при бесконечном повторении

Дана строка str , обозначающая последовательность ходов. Задача состоит в том, чтобы проверить, повторяются ли движения бесконечное число раз, то движения будут связаны по круговой траектории или нет. Движения могут быть следующих видов:

• «G»: идите прямо 1 единицу;
• «L»: повернуть на 90 градусов влево;
• «R»: повернуться на 90 градусов вправо.

Примеры:

Input: str = “GGLLGG”
Output: true
Explanation: The movements are: (0, 0) to (0, 2); turn 180 degrees; and then returns to (0, 0).
When repeating these instructions, the movements are bounded in a circular path.

Input: str = “GG”
Output: false
Explanation: The moves will go infinitely in forward direction only.

Input: str = “GL”
Output: true
Explanation: The moves upon infinite repetition are
from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> . . .
Thus bounded in this circular path.

Подход: При любом движении можно смотреть в любом из четырех направлений: «Север», «Юг», «Восток» и «Запад». Идея состоит в том, чтобы изначально стоять в позиции (0, 0) и смотреть на север . Так как инструкция дается бесконечное количество раз, то движения приведут к круговому пути, если после некоторых инструкций он вернется обратно в исходную точку.

Это возможно только в том случае, если после одной инструкции его направление меняется или он возвращается в исходное положение.

               N

              |

              |

 W ————– E

              |

              |

              S 

Чтобы определить положение и направление робота после каждой команды, добавьте или вычтите определенные значения из его положения в зависимости от направления.

Вот как будет выглядеть направление и движение для каждого направления:

Выполните шаги, указанные ниже.

• Сохраните направления в виде вектора . Поскольку начальная позиция находится в (0, 0) , направление берется против часовой стрелки для расчета следующей позиции. Итак, вектор равен {N, W, S, E} .
• Инициализируйте i равным 0 , чтобы отслеживать вращение. Здесь 0 представляет начальное направление. Если в конце выполнения он равен 0, а позиция не является начальной позицией, функция вернет false.
• Инициализируйте x и y равными 0 , поскольку их начальное положение равно (0, 0).
• Запустите цикл для повторения инструкций одну за другой.
• Проверьте правое или левое вращение. Увеличьте i на 1 для левого и на 3 для правого вращения. (3 для правого, потому что один правый поворот равен 3 левым поворотам, и здесь направления считаются против часовой стрелки)
• Если он идет прямо, добавьте значения x и y из вектора, соответствующего i ^-му направлению.
• Конец цикла.
• Проверьте, ведут ли движения обратно в исходное положение или направление отличается от начального. Если любое из этих двух условий истинно, вернуть true. В противном случае вернуть ложь.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N), где N — длина строки.
Вспомогательное пространство: O(1)