Single-Row Keyboard Algorithms to Estimate the Finger Moving Tim
- 时间:2020-09-20 13:49:13
- 分类:网络文摘
- 阅读:89 次
There is a special keyboard with all keys in a single row. Given a string keyboard of length 26 indicating the layout of the keyboard (indexed from 0 to 25), initially your finger is at index 0. To type a character, you have to move your finger to the index of the desired character. The time taken to move your finger from index i to index j is |i – j|. You want to type a string word. Write a function to calculate how much time it takes to type it with one finger.
Example 1:
Input: keyboard = “abcdefghijklmnopqrstuvwxyz”, word = “cba”
Output: 4
Explanation: The index moves from 0 to 2 to write ‘c’ then to 1 to write ‘b’ then to 0 again to write ‘a’.
Total time = 2 + 1 + 1 = 4.Example 2:
Input: keyboard = “pqrstuvwxyzabcdefghijklmno”, word = “leetcode”
Output: 73Constraints:
- keyboard.length == 26
- keyboard contains each English lowercase letter exactly once in some order.
- 1 <= word.length <= 10^4
- word[i] is an English lowercase letter.
Using Hash Map to Record the Key Indices
We can use a hash map to record the position/index of the keys. Then, we can iterate the word, simulating the fingers moving character by character, adding up the total time required.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution { public: int calculateTime(string keyboard, string word) { unordered_map<char, int> data; for (int i = 0; i < keyboard.size(); ++ i) { data[keyboard[i]] = i; } int r = data[word[0]]; for (int i = 1; i < word.size(); ++ i) { r += abs(data[word[i]] - data[word[i - 1]]); } return r; } }; |
class Solution { public: int calculateTime(string keyboard, string word) { unordered_map<char, int> data; for (int i = 0; i < keyboard.size(); ++ i) { data[keyboard[i]] = i; } int r = data[word[0]]; for (int i = 1; i < word.size(); ++ i) { r += abs(data[word[i]] - data[word[i - 1]]); } return r; } };
Using a static counter array
As the input keyboard has exactly 26 characters, we can use O(1) static counter array that is of size 26.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution { public: int calculateTime(string keyboard, string word) { int data[26]; for (int i = 0; i < keyboard.size(); ++ i) { data[keyboard[i] - 97] = i; } int r = data[word[0] - 97]; for (int i = 1; i < word.size(); ++ i) { r += abs(data[word[i] - 97] - data[word[i - 1] - 97]); } return r; } }; |
class Solution { public: int calculateTime(string keyboard, string word) { int data[26]; for (int i = 0; i < keyboard.size(); ++ i) { data[keyboard[i] - 97] = i; } int r = data[word[0] - 97]; for (int i = 1; i < word.size(); ++ i) { r += abs(data[word[i] - 97] - data[word[i - 1] - 97]); } return r; } };
Both implementations run at O(N) time where N is the length of the word.
Python Implementation of Single-Row Keyboard Algorithm
In Python, we can use the enumerate function to record the index, and we can then accumulate the costs by iterating the keys. A previous distance to type the key (initialised to zero) is remembered.
1 2 3 4 5 6 7 8 9 10 11 | class Solution: def calculateTime(self, keyboard: str, word: str) -> int: d = {} for x, y in enumerate(keyboard): d[y] = x # remember the index for each keys. ans = 0 prev = 0 for i in word: ans += abs(d[i] - prev) prev = d[i] return ans |
class Solution: def calculateTime(self, keyboard: str, word: str) -> int: d = {} for x, y in enumerate(keyboard): d[y] = x # remember the index for each keys. ans = 0 prev = 0 for i in word: ans += abs(d[i] - prev) prev = d[i] return ans
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:饮食健康与胃病食疗(二):慢性胃炎的饮食调理 饮食健康与胃病食疗(三):这样饮食降低胃癌风险 冬至时节,常吃这几种传统美食可补阳、防寒! 只有这样吃大蒜才能杀菌防癌,以前你吃对了吗 丝瓜营养丰富,其对人体的保健功效如此之多 患有胃病的人常吃这些食物,可以帮助调理好胃 山药营养丰富食疗价值高,助爱美女性吃出好身材 糖尿病患者常有这些饮食误区,朋友们注意啦! 网络上流传甚广的垃圾食品方便面有毒、致癌的传闻是真的吗? 经常吃核桃仁可以补脑是真的吗 一天吃多少核桃才健康
- 评论列表
-
- 添加评论