Given 3 input strings S1, S2, S3 for example take s1 = "hard" s2 = "work", s3 = "success"
assign numeric values (0-9) to each of the characters in these strings such that equation s1 + s2 = s3 holds true. Constraints
are that all occurrence of a letter should be assigned the same digit. Return -1 if not possible. I told the algo using backtracking but he required in polynomial time for which I had no idea.
---------------------------------------------------------------------
Similar to Sudoku Solver, however, this problem is more complicated.
Assume s1.length == s2.length, we could write a simple code like this：
#include
#include
#include
#include
#include
using namespace std;
class Solution {
public:
unordered_map res;
bool exist[10];
bool isValid(string& s1, string& s2, string& s3, int num, int depth, int x, int y) {
int s1len = s1.length(), s2len = s2.length(), s3len = s3.length();
return (x != y)&&(y != num%10)&&(x != num%10)&&(!exist[x] && res[s1[s1len-depth]] == -1 || res[s1[s1len-depth]] == x)&&(!exist[y] && res[s2[s2len-depth]] == -1 || res[s2[s2len-depth]] == y)&&(!exist[num%10] && res[s3[s3len-depth]] == -1 || res[s3[s3len-depth]] == num%10);
}
void saveFlg(string& s1, string& s2, string& s3, int depth, int x, int y, int z, int& saveX, int& saveY, int& saveZ,bool& saveFlgX, bool& saveFlgY, bool& saveFlgZ) {
int s1len = s1.length(), s2len = s2.length(), s3len = s3.length();
saveX = res[s1[s1len-depth]], saveY = res[s2[s2len-depth]], saveZ = res[s3[s3len-depth]];
saveFlgX = exist[x], saveFlgY = exist[y], saveFlgZ = exist[z];
}
void setFlg(string& s1, string& s2, string& s3, int depth, int x, int y, int z, bool flgX, bool flgY, bool flgZ) {
int s1len = s1.length(), s2len = s2.length(), s3len = s3.length();
res[s1[s1len-depth]] = x, res[s2[s2len-depth]] = y,res[s3[s3len-depth]] = z;
exist[x] = flgX, exist[y] = flgY, exist[z] = flgZ;
}
void recoverFlg(string& s1, string& s2, string& s3, int depth,int& saveX, int& saveY, int& saveZ,bool& saveFlgX, bool& saveFlgY, bool& saveFlgZ) {
setFlg(s1,s2,s3,depth,saveX,saveY,saveZ,saveFlgX,saveFlgY,saveFlgZ);
}
bool dfs(string& s1, string& s2, string& s3, int carry, int depth) {
int s1len = s1.length(), s2len = s2.length(), s3len = s3.length(),i,j,x = 0,y = 0, saveX, saveY, saveZ;
bool saveFlgX, saveFlgY, saveFlgZ;
for (i = 0; i <= 9; ++i)
for (j = 0; j <=9; ++j) {
int num = i + j + carry;
if (isValid(s1, s2, s3, num, depth, i, j)) {
//saveFlg(s1, s2, s3, depth, i, j, num%10,saveX,saveY,saveZ,saveFlgX,saveFlgY,saveFlgZ);
saveX = res[s1[s1len-depth]], saveY = res[s2[s2len-depth]], saveZ = res[s3[s3len-depth]], saveFlgX = exist[i], saveFlgY = exist[j], saveFlgZ = exist[num%10];
setFlg(s1, s2, s3, depth, i, j, num%10, true, true, true);
if (depth == s2len) {
if (s3len - s2len == 0 && num / 10 == 0)
return true;
else if (s3len > s2len && (res[s3[s3len-depth-1]] == -1 && !exist[num/10] || res[s3[s3len-depth-1]] == num/10)) {
res[s3[s3len-depth-1]] = num/10;
exist[num/10] = true;
return true;
}
}
else {
if (dfs(s1, s2, s3, num / 10, depth + 1))
return true;
}
res[s1[s1len-depth]] = saveX, res[s2[s2len-depth]] = saveY, res[s3[s3len-depth]] = saveZ, exist[i] = saveFlgX, exist[j] = saveFlgY,exist[num%10] = saveFlgZ;
//recoverFlg(s1, s2, s3, depth,saveX,saveY,saveZ,saveFlgX,saveFlgY,saveFlgZ);
}
}
return false;
}
bool check(string& s1, string& s2, string& s3) {
int s1len = s1.length(), s2len = s2.length(), s3len = s3.length(),i,j;
string s = s1 + s2 + s3;
for (i = 0; i < s.length(); ++i)
if (res.find(s[i]) == res.end()) {
res.insert(make_pair(s[i],-1));
}
memset(exist, false, sizeof(exist));
if (res.size() >10 ||s1len > s3len)
return false;
int s1s2len = max(s1len, s2len);
for (i = 0; i < (s3len - s1s2len - 1); ++i) {
if (res[s3[i]] == -1 && !exist[0]) {
res[s3[i]] = 0;
exist[0] = true;
}
else if (exist[0])
return false;
}
return s1len < s2len ? dfs(s2, s1, s3, 0, 1):dfs(s1, s2, s3, 0, 1);
}
};
int main() {
Solution s;
string a = "SEND", b = "MORE", c = "MONEY";
bool res = s.check(a,b,c);
return 0;
}
Take notice of recoverFlg, I gave wrong parameters. So the simplified code is:
#include
#include
#include
#include
#include
using namespace std;
class Solution {
public:
unordered_map res;
bool exist[10];
bool isValid(string& s1, string& s2, string& s3, int num, int depth, int x, int y) {
int s1len = s1.length(), s2len = s2.length(), s3len = s3.length();
return (x != y)&&(y != num%10)&&(x != num%10)&&(!exist[x] && res[s1[s1len-depth]] == -1 || res[s1[s1len-depth]] == x)&&(!exist[y] && res[s2[s2len-depth]] == -1 || res[s2[s2len-depth]] == y)&&(!exist[num%10] && res[s3[s3len-depth]] == -1 || res[s3[s3len-depth]] == num%10);
}
void setFlg(string& s1, string& s2, string& s3, int depth, int x, int y, int z, bool flgX, bool flgY, bool flgZ) {
int s1len = s1.length(), s2len = s2.length(), s3len = s3.length();
res[s1[s1len-depth]] = x, res[s2[s2len-depth]] = y,res[s3[s3len-depth]] = z;
exist[x] = flgX, exist[y] = flgY, exist[z] = flgZ;
}
bool dfs(string& s1, string& s2, string& s3, int carry, int depth) {
int s1len = s1.length(), s2len = s2.length(), s3len = s3.length(),i,j,x = 0,y = 0, saveX, saveY, saveZ;
bool saveFlgX, saveFlgY, saveFlgZ;
for (i = 0; i <= 9; ++i)
for (j = 0; j <=9; ++j) {
int num = i + j + carry;
if (isValid(s1, s2, s3, num, depth, i, j)) {
saveX = res[s1[s1len-depth]], saveY = res[s2[s2len-depth]], saveZ = res[s3[s3len-depth]], saveFlgX = exist[i], saveFlgY = exist[j], saveFlgZ = exist[num%10];
setFlg(s1, s2, s3, depth, i, j, num%10, true, true, true);
if (depth == s2len) {
if (s3len - s2len == 0 && num / 10 == 0)
return true;
else if (s3len > s2len && (res[s3[s3len-depth-1]] == -1 && !exist[num/10] || res[s3[s3len-depth-1]] == num/10)) {
res[s3[s3len-depth-1]] = num/10;
exist[num/10] = true;
return true;
}
}
else {
if (dfs(s1, s2, s3, num / 10, depth + 1))
return true;
}
res[s1[s1len-depth]] = saveX, res[s2[s2len-depth]] = saveY, res[s3[s3len-depth]] = saveZ, exist[i] = saveFlgX, exist[j] = saveFlgY,exist[num%10] = saveFlgZ;
}
}
return false;
}
bool check(string& s1, string& s2, string& s3) {
int s1len = s1.length(), s2len = s2.length(), s3len = s3.length(),i,j;
string s = s1 + s2 + s3;
for (i = 0; i < s.length(); ++i)
if (res.find(s[i]) == res.end()) {
res.insert(make_pair(s[i],-1));
}
memset(exist, false, sizeof(exist));
if (res.size() >10 ||s1len > s3len)
return false;
int s1s2len = max(s1len, s2len);
for (i = 0; i < (s3len - s1s2len - 1); ++i) {
if (res[s3[i]] == -1 && !exist[0]) {
res[s3[i]] = 0;
exist[0] = true;
}
else if (exist[0])
return false;
}
return s1len < s2len ? dfs(s2, s1, s3, 0, 1):dfs(s1, s2, s3, 0, 1);
}
};
int main() {
Solution s;
string a = "SEND", b = "MORE", c = "MONEY";
bool res = s.check(a,b,c);
return 0;
}
