tianyang19910112
BAN USERThe code is wrong, For example
A->B
C->D
A->C
Your code can't handle this situation..
Assume s1.length == s2.length, I give a simplied code. Take s1.length != s2.length, more code is needed.
#include <unordered_map>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
class Solution {
public:
unordered_map<char,int> 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;
}
since each number is at a distance k from its actual position, there are an even number of elements and to sort all one has to do is swap.
- tianyang19910112 March 07, 2014Let N be the size of the array
The size of the array is at least 2k
for(int i=0; i<k; ++i)
swap(a[i], a[i+k]);
if(4k <= N)
for(int i=0; i<k; ++i)
swap(a[2k+i], a[2k+i+k]);
and so on till the end of the array , i.e., divide the array into blocks of size 2k,
and inside each block swap the elements which are at a distance of k