通过键盘按下输入文本的最短路径

本文关键字：文本 最短路径 输入 键盘 | 更新日期: 2023-09-27 18:18:49

我从用户获得自定义字符串。现在我需要设计在键盘上按下这个字符串的最短路线，其中包括9个按钮。

注意:

  • 解决方案字母应按字母顺序排列，即a, b, c, d, e，…
  • 每个数字应该至少包含一个键盘字符

如果input text = 'hello'

  1. a、b、c、d
  2. e, f, g
  3. h, i, j, k
  4. l, m, n
  5. 0, p, q
  6. r, s, t
  7. u, v, w
  8. x, y
    9. z

或

  1. a、b、c、d
  2. e, f, g
  3. h, i, j, k
  4. l, m, n
  5. o
  6. p
    7. q
  8. r
  9. s, t, u, v, w, x, y, z

使用这个键盘，我需要按3,2,4,4,5来输入'hello'

所以如果你想用这个设计的键盘输入'hello'，你只需要按5个键盘按钮，因为这是最少的键数。

我认为这个问题可以用贪心方法或者回溯算法来解决。

通过键盘按下输入文本的最短路径

让我们将字母表泛化为{1，…，n}。设k为键的个数。对于1≤i <j≤k，一个可能的键{i，…，j}的代价(>i + 2fi+1 +…+ (j - i+1) fj，其中fi是字母i出现的频率，我们正在寻找包含k个键的最小代价精确覆盖。

这个问题有如下最优子结构:固定一个任意最优解并移除上面有{m + 1，…，n}的键。结果是具有k - 1个键和字母{1，…，m}的问题的最优解;否则，我们可以通过重新排列前k - 1个键来改进第一个最优解。

因此，我们可以应用动态规划。对于每一个0≤i≤n和每一个0≤j≤k，计算{1，…，i}有j个键的最优排列。这种排列的代价Ci,j满足递归式

C0，对于所有j≥0
，j = 0Ci,0 =∞对于所有i> 0
Ci,j = min0≤i' <我子> ’,j - 1 + C <子>我,j ),

其中ca,b是键{a，…，b}的代价。可以从最优参数序列i'中恢复排列本身。

每个有效的键盘对应一个26位数字，其中恰好有9位设置为1。只有2042975个有效的组合可以尝试，在其他需要更多思考的方法之前，应该首先尝试暴力破解。这个算法是这样的伪代码:

int best_score = int.max
list<int> keypads
for int mask between 1 and 1<<26
    if bit_count(mask) != 9 or mask ends in 1 continue
    int lookup[26]
    int p = 1
    for int i between 0 and 26
        lookup[i] = p
        if mask's bit i is set to 1, p = 1 ; otherwise, p = p + 1
    int total = 0
    for each char ch in word
        total = total + lookup[ch]
    if total < best
        keypads = new list {mask}
        best = total
    else if total == best
        keypads.add(mask)
print best, keypads
相关文章：