Help me to solve verbal arithmetic puzzle problem

help
, , ,
1

I’m currently tackling the problem provided on LeetCode, which can be found here.

Could someone assist me in identifying any errors or gaps in logic within my solution?

class Solution {
public:
    bool isSolvable(vector<string>& words, string result) {
        unordered_map<char, int> mp;
        for(auto it:words){
            int size=it.size();
            for(int i=0;i<size;i++){
                if(mp.find(it[i])==mp.end()){
                    mp[it[i]]=mp.size();
                }
            }
        }
        int size=result.size();
        for(int i=0;i<size;i++){
            if(mp.find(result[i])==mp.end()){
                mp[result[i]]=mp.size();
            }
        }
        string num="0123456789";

       //generate all permutation
        do{
            int num1=0;
            int resultNum = 0;
        //if first digit is 0
            if(num[mp[result[0]]]=='0'){
                continue;
            }
            for(auto it:result){
                int currInd=mp[it];
                int currDigit=num[currInd]-'0';
                resultNum=resultNum*10+currDigit;
            }
            for(int i=0;i<words.size();i++){
                int currNum=0;
               //if first digit is 0
                if(num[mp[words[i][0]]]=='0'){
                    currNum=INT_MAX;
                    break;
                }
        //generate number from current permutation
                for(auto it:words[i]){
                    int currInd=mp[it];
                    int currDigit=num[currInd]-'0';
                    currNum=currNum*10+currDigit;
                }
                num1+=currNum;
                if(num1>resultNum)break;
            }
            if(num1==resultNum)return true;
        }while(next_permutation(num.begin(),num.end()));
        return false;
    }
};
2

I don’t think there’s a gasp in you logic (the way you sum up the letters is quite obscure, but correct), and I also tested using the examples provided in the same link, and does what is supposed to.

You use the features of std::next_permutation(), which makes me wonder… Do you get TLE?

Although std::next_permutation() is relatively fast perform O(N/2) at worst, the problem begins when you try all the permutations and doesn’t find a result, like:

Input: words = [“LEET”,“CODE”], result = “POINT”

It should run all the N! permutations, where N is the size of your unordered_map, so the complexity of your code is O(N!) and that’s crazy.

If you are getting TLE, I guess you should try another focus instead of brute force.

For example, in that “LEET” + “CODE” = “POINT”. If there was an answer, you know by first sight that E must’ve been ‘0’ so the T in Leet remains in Point.

3

Thank you for your reply.
With given constraints, my solution will exceed 10^8 limit (My solution's TC: 10! *(7+5*7) = 152,409,600). I guess that’s why it is giving TLE. Anyways let me try another approach.

4

Another thing that I’m spotting is that no word can begin with 0.

So, for the set {L,E,T,C,O,D,P,I,N}
If all the permutations were vaild, we should do
10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 = 3,628,800

But L,C and P cannot be 0, the actual valid permutations are:
10* 9 * 8 * 7 * 6 * 5 * (4-1) * (3-1) * (2-1) = 907,200

Considering that there would be a corner case when you could have 2 words, and the following talings:

A + B = A
or
B + B = B
B must be 0

The valid permutations reduce to:
10* 9 * 8 * 7 * 6 * (5-1) * (4-1) * (3-1) = 725,760

Moreover, AAB + BCB = EEB, B should be 0, but 0 can lead a number, so you categorically know it’s impossible.

It’s a fun problem. :grin: