C ++中的口头算术难题

假设我们有一个方程，表达式用左侧的单词表示，结果用右侧表示。我们必须检查该方程式在以下规则下是否可求解-

每个字符被解码为一位数字（0到9）。
每对不同的字符必须映射到不同的数字。
每个单词[i]和结果都被解码为一个数字，其中不存在任何前导零。
左侧的数字总和将等于右侧的数字。
我们将检查方程是否可解。

因此，如果输入像单词= [“ SEND”，“ MORE”]，结果=“ MONEY”，则输出将为True，就像我们按以下方式映射字母一样：映射'S'-> 9，'E '-> 5，'N'-> 6，'D'-> 7，'M'-> 1，'O'-> 0，'R'-> 8，'Y'->'2'，然后“ SEND” +“ MORE” =“ MONEY”与9567 + 1085 = 10652相同。

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

定义大小为10的数组i2c，大小为26的数组c2i和另一个数组w
定义一个函数solve()，它将使用idx，l，sum，
如果l与r的大小相同，则-

当总和等于0时返回true

如果idx与w的大小相同，则-

如果l与r的大小相同，并且总和10为0，则-
c2i [r [l]-'A'的ASCII] =和模10
i2c [sum mod 10] = r [l]-'A'的ASCII
temp：= solve（0，l + 1，sum / 10）
c2i [r [l]-'A'的ASCII] =-1
i2c [sum mod 10] =-1
返回温度
返回假
如果c2i [r [l]-“ A”的ASCII]与sum mod 10相同，则-
return resolve（0，l + 1，sum / 10）

如果c2i [r [l]-“ A”的ASCII]不等于-1，则-
否则，当i2c [sum mod 10]与-1相同时，则-
返回假

如果l> = w [idx]的大小，则-

返回solve（idx + 1，l，sum）

如果c2i [w [idx，l]-'A']不等于-1，则-

返回假
如果l与w [idx]的大小相同，并且c2i [w [idx，l]-'A']的ASCII等于0，则-
returnsolve（idx + 1，l，sum + c2i [w [idx，l]-'A'的ASCII]）

对于初始化i：= 0，当i <10时，更新（将i增加1），执行-

返回真
忽略以下部分，跳至下一个迭代
忽略以下部分，跳至下一个迭代
如果i2c [i]不等于-1，则-
如果i等于0，l等于w [idx]的大小，则-
i2c [i]：= w [idx，l]-'A'的ASCII
c2i [w [idx，l]-'A'的ASCII] = i
temp：= solve（idx + 1，l，sum + i）
i2c [i]：= -1
c2i [w [idx，l]-'A'的ASCII] =-1
如果temp不为零，则-

返回假
从主要方法中执行以下操作-
用-1填充i2c和c2i
反转数组结果
对于初始化i：= 0，当i <字长时，更新（将i增加1），执行-

返回假
如果word [i]的大小>结果的大小，则-
反转数组单词[i]

r：=结果，w：=单词
返回solve(0,0,0)

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

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   char i2c[10];
   int c2i[26];
   vector<string> w;
   string r;
   bool solve(int idx, int l, int sum){
      if (l == r.size()) {
         return sum == 0;
      }
      if (idx == w.size()) {
         if (c2i[r[l] - 'A'] != -1) {
            if (c2i[r[l] - 'A'] == sum % 10) {
               return solve(0, l + 1, sum / 10);
            }
         }
         else if (i2c[sum % 10] == -1) {
            if (l == r.size() - 1 && sum % 10 == 0)
            return false;
            c2i[r[l] - 'A'] = sum % 10;
            i2c[sum % 10] = r[l] - 'A';
            bool temp = solve(0, l + 1, sum / 10);
            c2i[r[l] - 'A'] = -1;
            i2c[sum % 10] = -1;
            return temp;
         }
         return false;
      }
      if (l >= w[idx].size()) {
         return solve(idx + 1, l, sum);
      }
      if (c2i[w[idx][l] - 'A'] != -1) {
         if (l == w[idx].size() - 1 && c2i[w[idx][l] - 'A'] == 0){
            return false;
         }
         return solve(idx + 1, l, sum + c2i[w[idx][l] - 'A']);
      }
      for (int i = 0; i < 10; i++) {
         if (i2c[i] != -1)
         continue;
         if (i == 0 && l == w[idx].size() - 1)
         continue;
         i2c[i] = w[idx][l] - 'A';
         c2i[w[idx][l] - 'A'] = i;
         bool temp = solve(idx + 1, l, sum + i);
         i2c[i] = -1;
         c2i[w[idx][l] - 'A'] = -1;
         if (temp)
         return true;
      }
      return false;
   }
   bool isSolvable(vector<string>& words, string result){
      memset(i2c, -1, sizeof(i2c));
      memset(c2i, -1, sizeof(c2i));
      reverse(result.begin(), result.end());
      for (int i = 0; i < words.size(); i++) {
         if (words[i].size() > result.size())
         return false;
         reverse(words[i].begin(), words[i].end());
      }
      r = result;
      w = words;
      return solve(0, 0, 0);
   }
};
main(){
   Solution ob;
   vector<string> v = {"SEND","MORE"};
   cout << (ob.isSolvable(v, "MONEY"));
}

输入值

{"SEND","MORE"}, "MONEY"

输出结果

基础教程