使用给定单行键盘计算输入单词所需时间

---

以下文章讨论了一种高效的方法来计算使用单行键盘输入单词的总时间。这是一个有趣的问题，之前在技术面试中被问到过。

问题陈述

考虑一种假设的情况，其中键盘上的所有按键都排成一行。第一个键的索引为 0，最后一个键的索引为 25。

对于给定的字符串“s”，计算在指定为“keyboard_layout”的特殊键盘布局上输入“s”的所有字符所需的时间。

从一个键移动到其相邻键需要单位时间。可以在两个方向上进行遍历。最初我们位于索引 0。

示例

输入

keyboard = "mnbvcxzqwertyuioplkjhgfdsa", word = "cat"

输出

39

解释

最初我们位于索引 0，即 m

要到达“c”，所需时间 = 4，因为 m>n>b>v>c

要到达“a”，所需时间 = 21，因为 c>x>z>q>w>e>r>t>y>u>i>o>p>k>j>h>g>f>d>s>a

要到达“t”，所需时间 = 14，因为 a>s>d>f>g>h>j>k>l>p>o>i>u>y>t

总时间 = 4 + 21 + 14 = 39

输入

keyboard “rfvcdewsxzaqtgbnhyujmkiolp”, word = “hat”

输出

24

解释

要到达“h”，所需时间 = 16

要到达“a”，所需时间 = 6

要到达“t”，所需时间 = 2

遵循与上述相同的逻辑。

总时间 = 16 + 6 + 2 = 24

输入

keyboard = “plmkoijnbhuygvcftrdxzsewaq”, word = “bat”

输出

32

解释

要到达“b”，所需时间 = 8

要到达“a”，所需时间 = 16

要到达“t”，所需时间 = 8

遵循与上述相同的逻辑。

总时间 = 8 + 16 + 8 = 24

解决方案方法

为了找到在给定的特殊单行键盘布局 keyboard_layout 上输入给定单词所需的时间，我们首先将要输入的单词和键盘布局存储在两个字符串变量中。

我们保持手指的先前位置和当前位置。输入每个字符所需的时间由 |curr_pos - prev_pos| 给出，并在每次迭代中添加到总时间中。每次迭代后，我们将 prev_pos 更新为 curr_pos。

伪代码

• 开始

• 从用户处读取输入字符串 keyboard 和 word

• 设置 time = 0 和 prev_pos = 0

• 对于 word 中的每个字符 c，执行以下操作

• 设置 curr_pos = keyboard.find(c)

• 设置 time = time + abs(curr_pos - prev_pos)

• 设置 prev_pos = curr_pos

• 输出 time 作为总的单词输入时间。

• 结束

干运行

keyboard = "qazwsxedcrfvtgbyhnujmikolp"
word = "well"
1. time = 0, prev_pos = 0
2. For each character in word:
   - For 'w':
      - curr_pos = 0
      - time += abs(3 - 0) = 3
      - prev_pos = 3
   - For 'e':
      - curr_pos = 3
      - time += abs(6 - 3) = 3
      - prev_pos = 6
   - For 'l':
      - curr_pos = 24
      - time += abs(24 - 6) = 18
      - prev_pos = 24
   - For 'l':
      - curr_pos = 24
      - time += abs(24 - 24) = 0
      - prev_pos = 24
3. Return time = 3 + 3 + 18 + 0 = 24

示例：C++ 程序

程序以输入字符串 keyboard_layout 为输入，该字符串表示具有所有按键排成一行的特殊键盘的布局，以及表示要输入的单词的字符串。程序计算输入单词所需的时间，其中将手指从一个键移动到另一个键所需的时间是其索引的绝对差值。程序通过调用函数 timeTaken() 返回输入单词的总时间。

示例

// C++ code to find the typing time for the word using a one row keyboard
#include <iostream>
#include <string>
using namespace std;

// To compute the time taken to type the word using a given single row keyboard, the following function is used.
int timeTaken(string keyboard_layout, string word){
   // Initialize time and previous position variables
   int time = 0, prev_pos = 0;
   // Iterate over each character in the word
   for (char c : word){
// Find the position of the current character in the keyboard_layout
      int curr_pos = keyboard_layout.find(c);
// Calculate the time taken to type the current character and add it to the total time
      time += abs(curr_pos - prev_pos);
      // Update the previous position to the current position
      prev_pos = curr_pos;
   }
   // Return the typing time for the word
   return time;
}
int main(){
   string keyboard_layout = "mnbvcxzqwertyuioplkjhgfdsa";
   string word = "tutorialspoint";
   // function call to calculate time taken to type word
   int time = timeTaken(keyboard_layout, word);
   // Print the result
   cout <<"Typing time for the word using a one row keyboard: " << time << endl;
   return 0;
}

输出

Typing time for the word using a one row keyboard: 87

时间和空间复杂度分析

时间复杂度：O(n)

• n = 要输入的给定单词的长度。

• 程序遍历 word 字符串中的每个字符，其长度为 n。

• 对于每个字符，它对 keyboard 字符串执行查找操作，其长度为 26（常数）。

• 因此，程序的时间复杂度 = O(n * 26) = O(n)。

空间复杂度：O(1)

• 程序使用固定数量的内存来存储 keyboard 和 word 字符串，以及一些整型变量。

• 这意味着程序的内存需求不会随着输入大小的增加而增加。

结论

本文讨论了一种高效的解决方案方法，用于计算使用给定的单行键盘输入单词所需的时间。通过示例解释了问题陈述，以便更好地理解。此外，解决方案方法包括伪代码、干运行、C++程序以及对解决方案时间和空间复杂度的深入分析，以便深入理解。