방정식이 있다고 가정하고 표현식은 왼쪽에 단어로 표시되고 결과는 오른쪽에 표시됩니다. 다음 규칙에 따라 방정식을 풀 수 있는지 확인해야 합니다. -
-
각 문자는 한 자리(0 ~ 9)로 디코딩됩니다.
-
서로 다른 문자의 모든 쌍은 서로 다른 숫자에 매핑되어야 합니다.
-
각 단어[i]와 결과는 선행 0이 없는 숫자로 디코딩됩니다.
-
왼쪽에 있는 숫자의 합은 오른쪽에 있는 숫자와 같습니다.
-
방정식을 풀 수 있는지 여부를 확인합니다.
따라서 입력이 단어 =["SEND","MORE"], 결과 ="MONEY"와 같은 경우 출력은 다음과 같이 문자를 매핑할 때와 같이 True가 됩니다. Map '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의 크기와 같으면 -
-
c2i[r[l] - 'A']의 ASCII가 -1과 같지 않으면 -
-
c2i[r[l] - 'A']의 ASCII가 합계 모드 10과 같으면 -
-
해결(0, l + 1, 합계 / 10)을 반환
-
-
-
그렇지 않으면 i2c[sum mod 10]이 -1과 같을 때 -
-
l이 r의 크기와 같고 합계 mod 10이 0과 같으면 -
-
거짓을 반환
-
-
c2i[r[l] - 'A'의 ASCII] =합계 모드 10
-
i2c[sum mod 10] =r[l] - 'A'의 ASCII
-
temp :=해결(0, l + 1, 합계 / 10)
-
c2i[r[l] - 'A'의 ASCII] =- 1
-
i2c[sum mod 10] =- 1
-
반환 온도
-
-
거짓을 반환
-
-
l>=w[idx]의 크기이면 -
-
해결(idx + 1, l, 합계)을 반환
-
-
c2i[w[idx, l] - 'A']가 -1과 같지 않으면 -
-
l이 w[idx] 및 c2i[w[idx, l]의 크기와 같으면 - 'A']의 ASCII가 0과 같으면 -
-
거짓을 반환
-
-
return solve(idx + 1, l, sum + c2i[w[idx, l] - 'A'의 ASCII])
-
-
initialize 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
-
임시 :=해결(idx + 1, l, 합계 + i)
-
i2c[i] :=-1
-
c2i[w[idx, l] - 'A'의 ASCII] =- 1
-
temp가 0이 아니면 -
-
true를 반환
-
-
-
거짓을 반환
-
주요 방법에서 다음을 수행하십시오 -
-
i2c 및 c2i를 -1로 채우기
-
배열 결과 반전
-
for initialize i :=0, i <단어 크기일 때 업데이트(i 1 증가), do−
-
단어의 크기[i]> 결과의 크기인 경우 -
-
거짓을 반환
-
-
배열 단어 반전[i]
-
-
r :=결과, w :=단어
-
해결(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" 출력
1