class Solution {
public:
int a[26];
bool vis[26],used[26];
char s[26];
bool Begin[26];
int mp[26];
int ans=0;
int B=0;
void dfs(int step,int k,vector<string>&words,string result)
{
if(ans)
return;
if(step==k)
{
int num=0;
for(int i=0;i<k;i++)
{
mp[s[i]-‘A‘]=a[num++];
}
int len=result.length();
int tmp=0,sum=0,tp=0;
for(int i=0;i<len;i++)
tp=tp*10+mp[result[i]-‘A‘];
for(int i=0;i<words.size();i++)
{
int l=words[i].size();
tmp=0;
for(int j=0;j<l;j++)
tmp=tmp*10+mp[words[i][j]-‘A‘];
sum+=tmp;
}
if(tp==sum)
ans=1;
return;
/*int add=0;
int len=result.length();
int stp=1;
int flag=1;
while(1)
{
int tmp=0;
for(int i=0;i<words.size();i++)
{
int l=words[i].size();
if(l>=0&&stp<=l)
{
tmp=tmp+mp[words[i][l-stp]-‘A‘];
}
tmp+=add;
add=tmp/10;
tmp=tmp%10;
}
if(tmp==0&&add==0)
break;
if(stp<=len&&tmp!=mp[result[len-stp]-‘A‘])
{
flag=0;
break;
}
stp++;
}
if(flag==1)
ans=1;
return;*/
}
for(int i=0;i<=9;i++)
{
if(!vis[i])
{
if(i==0&&Begin[s[step]-‘A‘]==1)
continue;
a[step]=i;
vis[i]=1;
dfs(step+1,k,words,result);
vis[i]=0;
}
}
}
bool isSolvable(vector<string>& words, string result) {
int p=0;
for(int i=0;i<words.size();i++)
{
Begin[words[i][0]-‘A‘]=1;
int len=words[i].length();
for(int j=0;j<len;j++)
{
if(!used[words[i][j]-‘A‘])
{
used[words[i][j]-‘A‘]=1;
s[p++]=words[i][j];
}
}
}
int len=result.length();
Begin[result[0]-‘A‘]=1;
for(int i=0;i<len;i++)
{
if(!used[result[i]-‘A‘])
{
used[result[i]-‘A‘]=1;
s[p++]=result[i];
}
}
dfs(0,p,words,result);
if(ans)
return true;
else
return false;
}
};
