Leetcode 1472 – Design Browser History

O desafio envolve “implementar” um historico de navegacao onde temos 3 operacoes: visit, back e forward, sendo bem simples e direto, as operacoes back e forward avancam/retornam no historico, a operacao visit deve acessar uma nova pagina a partir da posicao atual, limpando o historico de acesso posterior.

Ex:

1 – input inicial, instanciando a classe com uma url:
BrowserHistory("www.google.com")

2 – visit
BrowserHistory.visit("www.facebook.com")

3 – visit
BrowserHistory.visit("www.linkedin.com")

4 – back 2 steps
BrowserHistory.back(2)

5 – forward 1 step
BrowserHistory.forward(1)

6 – visit www.youtube.com
BrowserHistory.visit("www.youtube.com")

Approach 1 – Usando doubly singled list (menos performático)

usando essa estrutura, cada no da lista ligada armazena o endereco do proximo/anterior

Sendo mais custoso por ter que percorrer um loop toda vez que usar as operacoes back/forward, complexidade de tempo e espaco O(n) onde n é o número de steps

Approach 2 – usando um array e um pointer para salvar as posicoes (mais performatico)

Como nao é necessário percorrer o array nas operações de back/forward, a complexidade de tempo é O(1) e a complexidade de espaço é O(n) onde n é o numero de urls visitadas usando o método visit()

原文链接：Leetcode 1472 – Design Browser History