Commit 2df36e1

authored

Design Browser History (#1472, java, py) + Add and Search Words Data Structure (#211, py)

* 1472. Design Browser History * problem 211: Design Add and Search Words Data Structure

1 parent 8d9e45c commit 2df36e1Copy full SHA for 2df36e1

File tree

+80

-0

lines changed

+80

-0

lines changed

Lines changed: 36 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,36 @@`
	`1`	`+class Trienode:`
	`2`	`+ def __init__(self):`
	`3`	`+ self.children = {}`
	`4`	`+ self.word = False`
	`5`	`+`
	`6`	`+class WordDictionary:`
	`7`	`+`
	`8`	`+ def __init__(self):`
	`9`	`+ self.root = Trienode()`
	`10`	`+`
	`11`	`+`
	`12`	`+ def addWord(self, word: str) -> None:`
	`13`	`+ ptr = self.root`
	`14`	`+ for ch in word:`
	`15`	`+ if ch not in ptr.children:`
	`16`	`+ ptr.children[ch] = Trienode()`
	`17`	`+ ptr = ptr.children[ch]`
	`18`	`+ ptr.word = True`
	`19`	`+`
	`20`	`+`
	`21`	`+ def search(self, word: str) -> bool:`
	`22`	`+ def dfs(j, root):`
	`23`	`+ curr = root`
	`24`	`+ for i in range(j, len(word)):`
	`25`	`+ ch = word[i]`
	`26`	`+ if ch == ".":`
	`27`	`+ for child in curr.children.values():`
	`28`	`+ if dfs(i+1, child):`
	`29`	`+ return True`
	`30`	`+ return False`
	`31`	`+ else:`
	`32`	`+ if ch not in curr.children:`
	`33`	`+ return False`
	`34`	`+ curr = curr.children[ch]`
	`35`	`+ return curr.word`
	`36`	`+ return dfs(0, self.root)`

Lines changed: 18 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,18 @@`
	`1`	`+class BrowserHistory:`
	`2`	`+`
	`3`	`+ def __init__(self, homepage: str):`
	`4`	`+ self.history = [homepage]`
	`5`	`+ self.ptr = 0`
	`6`	`+`
	`7`	`+ def visit(self, url: str) -> None:`
	`8`	`+ self.ptr += 1`
	`9`	`+ self.history = self.history[:self.ptr]`
	`10`	`+ self.history.append(url)`
	`11`	`+`
	`12`	`+ def back(self, steps: int) -> str:`
	`13`	`+ self.ptr = max(0, self.ptr - steps)`
	`14`	`+ return self.history[self.ptr]`
	`15`	`+`
	`16`	`+ def forward(self, steps: int) -> str:`
	`17`	`+ self.ptr = min(len(self.history) - 1, self.ptr + steps)`
	`18`	`+ return self.history[self.ptr]`

Lines changed: 26 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,26 @@`
	`1`	`+class BrowserHistory {`
	`2`	`+ private List<String> history;`
	`3`	`+ private int ptr;`
	`4`	`+`
	`5`	`+ public BrowserHistory(String homepage) {`
	`6`	`+ this.history = new ArrayList<>();`
	`7`	`+ this.history.add(homepage);`
	`8`	`+ this.ptr = 0;`
	`9`	`+ }`
	`10`	`+`
	`11`	`+ public void visit(String url) {`
	`12`	`+ this.ptr++;`
	`13`	`+ this.history = this.history.subList(0, this.ptr);`
	`14`	`+ this.history.add(url);`
	`15`	`+ }`
	`16`	`+`
	`17`	`+ public String back(int steps) {`
	`18`	`+ this.ptr = Math.max(0, this.ptr - steps);`
	`19`	`+ return this.history.get(this.ptr);`
	`20`	`+ }`
	`21`	`+`
	`22`	`+ public String forward(int steps) {`
	`23`	`+ this.ptr = Math.min(this.history.size() - 1, this.ptr + steps);`
	`24`	`+ return this.history.get(this.ptr);`
	`25`	`+ }`
	`26`	`+}`

Comments

(0)