from typing import NamedTuple ''' Given a keyboard represented as a matrix and a word, return the shortest path that would spell out the word starting from the top left corner of the matrix. Example: Keyboard: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z * * Word: DART Returns: [ (V: 0, H: 3), (V: 0, H: -3), (V: 2, H: 3), (V: 0, H: 2), ] ''' ## # Example: Path(1, -3) for +1 vertical change and -3 horizontal change ## class Path(NamedTuple): V: int # vertical change... UP: V < 0; Down: V >= 0 H: int # horizontal change... Left: H < 0; Right: H >= 0 def get_word_journey(keyboard, word): # complexity would O(mn) for naive solution # complexity will be O(m+n) for an optimized solution with hashmaps output = [] # convert the keyboard to a dictionary for O(1) access time char_pos = {char: (row, col) for row in range(len(keyboard)) for col in range(len(keyboard[row])) if keyboard[row][col] != '*'} if not word or any(char not in char_pos for char in word): return result prev_pos = (0, 0) for char in word: curr_pos = char_pos[char] current_vh = Path(curr_pos[0] - prev_pos[0], curr_pos[1] - prev_pos[1]) output.append(current_vh) prev_pos = curr_pos return output