This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

describe

There is a special typewriter with lowercase English letters ‘a’ to ‘z’ arranged in a circle with a pointer. A character can only be typed if the pointer is pointing to that character. The pointer is initially pointing to the character ‘a’.

Each second, you may perform one of the following operations:

  • Move the pointer one character counterclockwise or clockwise.
  • Type the character the pointer is currently on.

Given a string word, return the minimum number of seconds to type out the characters in word.

Example 1:

Input: word = "abc"
Output: 5
Explanation: 
The characters are printed as follows:
- Type the character 'a' in 1 second since the pointer is initially on 'a'.
- Move the pointer clockwise to 'b' in 1 second.
- Type the character 'b' in 1 second.
- Move the pointer clockwise to 'c' in 1 second.
- Type the character 'c' in 1 second.
Copy the code

Example 2:

Input: word = "bza"
Output: 7
Explanation:
The characters are printed as follows:
- Move the pointer clockwise to 'b' in 1 second.
- Type the character 'b' in 1 second.
- Move the pointer counterclockwise to 'z' in 2 seconds.
- Type the character 'z' in 1 second.
- Move the pointer clockwise to 'a' in 1 second.
- Type the character 'a' in 1 second.
Copy the code

Example 3:

Input: word = "zjpc" Output: 34 Explanation: The characters are printed as follows: - Move the pointer counterclockwise to 'z' in 1 second. - Type the character 'z' in 1 second. - Move the pointer clockwise to 'j' in 10 seconds. - Type the character 'j' in 1 second. - Move the pointer clockwise to 'p' in 6 seconds. - Type the character 'p' in 1 second. - Move the pointer counterclockwise to 'c' in 13 seconds. - Type the character 'c'  in 1 second.Copy the code

Note:

1 <= word.length <= 100
word consists of lowercase English letters.
Copy the code

parsing

When the pointer points to a letter, the letter needs to be printed. At first, the pointer points to the letter A.

The disk can rotate clockwise or counterclockwise, and we can do two things at a time:

  • Rotate the disk clockwise or counterclockwise so that the pointer points to a character in word. It takes a second to move a character and a few seconds to move it
  • It only takes 1 second to print this character

Let’s calculate the minimum number of seconds it takes to print the word.

In fact, this problem is very simple, is to traverse each character in word, and then find the minimum number of pointer movement from the last character to the next character, can be clockwise or counterclockwise, and then add up all the pointer movement time and the printing time of the letter. The key is to calculate clockwise and counterclockwise time.

answer

class Solution(object): def minTimeToType(self, word): """ :type word: str :rtype: int """ result = 0 for i, letter in enumerate(word): if i == 0: result += 1 + min(ord(letter)-ord('a'), 122-ord(letter)+1) else: If ord(letter) > ord(word[i-1]): result += 1 + min(ord(letter)-ord(word[i-1]), 122-ord(letter)+1+ord(word[i-1])-97) elif ord(letter) < ord(word[i-1]): result += 1 + min(ord(word[i-1])-ord(letter), 122-ord(word[i-1])+1+ord(letter)-97) else: result += 1 return resultCopy the code

The results

Runtime: 41 ms, Given each node in Python online submissions for Minimum Time to Type Word Using Special Typewriter. Memory Usage: Submissions in Python online submissions for Minimum Time to Type Word Using Special Typewriter.Copy the code

parsing

In fact, the easier way, using greedy algorithm can be solved.

answer

class Solution(object):
    def minTimeToType(self, word):
        """
        :type word: str
        :rtype: int
        """
        s = "abcdefghojklmnopqrstuvwxyz"
        result = 0
        cur = "a"
        for letter in word:
            if cur == letter:
                result += 1
                continue
            result += min(abs(ord(letter)-ord(cur)),26-abs(ord(letter)-ord(cur))) + 1
            cur = letter
        return result
Copy the code

The results

Runtime: 20 ms, Faster than 73.38% of Python online submissions for Minimum Time to Type Word Using Special Typewriter. Memory Usage: Submissions in Python online submissions for Minimum Time to Type Word Using Special Typewriter.Copy the code

Original link: leetcode.com/problems/mi…

Your support is my biggest motivation