Skip to content

Instantly share code, notes, and snippets.

@ylt6

ylt6/1320.py

Last active March 10, 2020 22:22
Download ZIP

Revisions

  1. ylt6 revised this gist Mar 10, 2020. 1 changed file with 11 additions and 11 deletions.
    22 changes: 11 additions & 11 deletions 1320.py
    View file
    Original file line number Diff line number Diff line change
    @@ -3,21 +3,22 @@
    from string import ascii_uppercase

    class Solution:

    def __init__(self):
    anchor = ord('A')
    self.keyboard = {c: ((ord(c) - anchor) // 6, (ord(c) - anchor) % 6) for c in ascii_uppercase}
    self.cache = {}
    self.memo = {}
    self.distance = lambda x, y: abs(self.keyboard[x][0] - self.keyboard[y][0]) + abs(
    self.keyboard[x][1] - self.keyboard[y][1])

    def reset_cache(self):
    self.cache = {}
    def reset(self):
    self.memo = {}

    def minimumDistance(self, word):
    def r_type_word(left_hand_in, right_hand_in, word_cursor, steps):
    hash_key = f'{left_hand_in}-{right_hand_in}-{word_cursor}-{steps}'
    if hash_key in self.cache:
    return self.cache[hash_key]
    if hash_key in self.memo:
    return self.memo[hash_key]

    if word_cursor == len(word):
    ret = steps
    @@ -35,30 +36,29 @@ def r_type_word(left_hand_in, right_hand_in, word_cursor, steps):
    else self.distance(right_hand_in, char)))
    )

    self.cache[hash_key] = ret
    self.memo[hash_key] = ret
    return ret

    return r_type_word(None, None, 0, 0)


    import unittest


    class UnitTest(unittest.TestCase):

    def test(self):
    s = Solution()
    self.assertEqual(s.minimumDistance('CAKE'), 3)
    s.reset_cache()
    s.reset()

    self.assertEqual(s.minimumDistance('HAPPY'), 6)
    s.reset_cache()
    s.reset()

    self.assertEqual(s.minimumDistance('NEW'), 3)
    s.reset_cache()
    s.reset()

    self.assertEqual(s.minimumDistance('YEAR'), 7)

    s.reset()

    if __name__ == '__main__':
    unittest.main()
  2. ylt6 created this gist Mar 10, 2020.
    64 changes: 64 additions & 0 deletions 1320.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,64 @@
    # https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/

    from string import ascii_uppercase

    class Solution:
    def __init__(self):
    anchor = ord('A')
    self.keyboard = {c: ((ord(c) - anchor) // 6, (ord(c) - anchor) % 6) for c in ascii_uppercase}
    self.cache = {}
    self.distance = lambda x, y: abs(self.keyboard[x][0] - self.keyboard[y][0]) + abs(
    self.keyboard[x][1] - self.keyboard[y][1])

    def reset_cache(self):
    self.cache = {}

    def minimumDistance(self, word):
    def r_type_word(left_hand_in, right_hand_in, word_cursor, steps):
    hash_key = f'{left_hand_in}-{right_hand_in}-{word_cursor}-{steps}'
    if hash_key in self.cache:
    return self.cache[hash_key]

    if word_cursor == len(word):
    ret = steps
    else:
    char = word[word_cursor]
    word_cursor += 1

    ret = min(
    r_type_word(char, right_hand_in, word_cursor,
    steps + (0 if not left_hand_in or left_hand_in == char
    else self.distance(left_hand_in, char))),

    r_type_word(left_hand_in, char, word_cursor,
    steps + (0 if not right_hand_in or right_hand_in == char
    else self.distance(right_hand_in, char)))
    )

    self.cache[hash_key] = ret
    return ret

    return r_type_word(None, None, 0, 0)


    import unittest


    class UnitTest(unittest.TestCase):

    def test(self):
    s = Solution()
    self.assertEqual(s.minimumDistance('CAKE'), 3)
    s.reset_cache()

    self.assertEqual(s.minimumDistance('HAPPY'), 6)
    s.reset_cache()

    self.assertEqual(s.minimumDistance('NEW'), 3)
    s.reset_cache()

    self.assertEqual(s.minimumDistance('YEAR'), 7)


    if __name__ == '__main__':
    unittest.main()