在C ++中用两个手指键入单词的最小距离

假设我们的键盘布局如下所示-

ACdEF
GHIĴK大号
MñOPQ[R
SŤUVWX
Yž



每个英语大写字母位于某个坐标处,例如,字母A放置在(0,0),字母B放置在(0,1),字母P放置在(2,3)字母Z放在(4,1)。现在,如果我们有一个单词,我们必须找到最小的总距离,以便仅用两个手指来键入这样的字符串。两个位置(x1,y1)和(x2,y2)之间的距离是| x1-x2 | + | y1-y2 |。我们可以从键盘上的任何位置开始。

因此,如果输入像“ HAPPY”,那么输出将为6,以H开头,因此成本为0,然后为A,因此从H到A的成本为2,然后为P,因此成本为0,然后再次P,成本为0,最后为Y,因此从P到Y的成本为4,因此总成本为6 + 4 = 10。

为了解决这个问题,我们将遵循以下步骤-

  • 定义一个映射备忘录

  • 定义一个函数getHash(),它将使用a,b,c,d,e,

  • 温度:= 0

  • 当a不为零时,请-

    • temp:= temp * 10 +一个mod 10,a:= a / 10

  • 当b不为零时,执行-

    • 温度:=温度* 10 + b mod 10,b:= b / 10

  • 当c不为零时,执行-

    • 温度:=温度* 10 + d mod 10,d:= d / 10

  • 当e不为零时,

    • temp:= temp * 10 + e mod 10,e:= e / 10

  • 返回温度

  • 定义一个方法getXY(),这将花费c

    • 定义一对ret

    • a:= c-'A'的ASCII

    • ret.second:= mod 6

    • ret.first:= a / 6

    • 返回ret

  • 定义一个函数getDist(),它将使用a,b,c,d,

  • 如果a与-1相同且b与-1相同,则-

    • 返回0

  • 返回|(b-d)+ | a-c ||

  • 定义一个功能solve(),它将使用x1,y1,x2,y2,word,idx,

  • 如果idx与单词的大小相同,则-

    • 返回0

  • 状态:= getHash(x1 + 2,y1 + 2,x2 + 2,y2 + 2,idx + 2)

  • 如果状态为备忘录,则-

    • 返回备忘录[状态]

  • 定义一对temp:= getXY(word [idx])

  • 回答:= 0

  • A:= getDist(x1,y1,temp.first,temp.second + solve(temp.first,temp.second,x2,y2,word,idx + 1))

  • B:= getDist(x2,y2,temp.first,temp.second + solve(x1,y1,temp.first,temp.second,word,idx + 1))

  • ans:= A和B的最小值

  • 返回备忘录[state] = ans

  • 从主要方法中执行以下操作-

  • returnsolve(-1,-1,-1,-1,word,0)

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   map<int, int> memo;
   int getHash(int a, int b, int c, int d, int e){
      int temp = 0;
      while (a) {
         temp = temp * 10 + a % 10;
         a /= 10;
      }
      while (b) {
         temp = temp * 10 + b % 10;
         b /= 10;
      }
      while (c) {
         temp = temp * 10 + c % 10;
         c /= 10;
      }
      while (d) {
         temp = temp * 10 + d % 10;
         d /= 10;
      }
      while (e) {
         temp = temp * 10 + e % 10;
         e /= 10;
      }
      return temp;
   }  
   pair<int, int> getXY(char c){
      pair<int, int> ret;
      int a = c - 'A';
      ret.second = a % 6;
      ret.first = a / 6;
      return ret;
   }
   int getDist(int a, int b, int c, int d){
      if (a == -1 && b == -1)
      return 0;
      return abs(b - d) + abs(a - c);
   }
   int solve(int x1, int y1, int x2, int y2, string word, int idx){
      if (idx == word.size())
      return 0;
      int state = getHash(x1 + 2, y1 + 2, x2 + 2, y2 + 2, idx + 2);
      if (memo.find(state) != memo.end())
      return memo[state];
      pair<int, int> temp = getXY(word[idx]);
      int ans = 0;
      int A = getDist(x1, y1, temp.first, temp.second) +
      solve(temp.first, temp.second, x2, y2, word, idx + 1);
      int B = getDist(x2, y2, temp.first, temp.second) + solve(x1,
      y1, temp.first, temp.second, word, idx + 1);
      ans = min(A, B);
      return memo[state] = ans;
   }
   int minimumDistance(string word){
      memo.clear();
      return solve(-1, -1, -1, -1, word, 0);
   }
};
main(){
   Solution ob;;
   cout << (ob.minimumDistance("HELLO"));
}

输入值

"HELLO"

输出结果

4