2 Keys Keyboard LeetCode solution in Python

1
class Solution:
2
    def minSteps(self, n: int) -> int:
3
        # at every step we can copy or paste
4
        # paste -> we need to know the current clipboard content (count)
5
        # copy -> set clipboard count to current screen count (we should consider it, if the last operation was paste)
6

7
        memo = {}
8

9
        def dfs(clipboard_count, screen_count):
10
            if (clipboard_count, screen_count) in memo:
11
                return memo[(clipboard_count, screen_count)]
12

13
            # we reached n, this is a valid option
14
            if screen_count == n:
15
                return 0
16

17
            # we passed n, not a valid option
18
            if screen_count > n:
19
                return float("inf")
20

21
            # paste or copy
22
            copy_opt = paste_opt = float("inf")
23

24
            # we should only paste if clipboard is not empty
25
            if clipboard_count > 0:
26
                paste_opt = dfs(clipboard_count, screen_count + clipboard_count)
27

28
            # we should consider copy only if the last operation was paste
29
            if screen_count > clipboard_count:
30
                copy_opt = dfs(screen_count, screen_count)
31

32
            # save to memo
33
            memo[(clipboard_count, screen_count)] = 1 + min(paste_opt, copy_opt)
34
            return memo[(clipboard_count, screen_count)]
35

36
        return dfs(0, 1)