ปริศนาคณิตศาสตร์ตัวอักษร (Verbal Arithmetic) ใน C++

คำอธิบายโจทย์

สมการคำพูด: words ด้านซ้าย + ... = result ด้านขวา แมปตัวอักษรเป็นตัวเลข 0-9 ตัวต่างต้องต่างตัวเลข ห้าม leading zero ตรวจสอบว่ามีคำตอบหรือไม่

ตัวอย่าง

words = ["SEND","MORE"], result = "MONEY" → True

แมป: S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2 → 9567+1085=10652

วิธีแก้ปัญหา

Backtracking คอลัมน์ต่อคอลัมน์ (จากหลักหน่วยขึ้นไป):

i2c[10]: digit → char, c2i[26]: char → digit
solve(idx, l, sum): idx=word index, l=column, sum=ผลรวมคอลัมน์นี้
ประมวลผลคอลัมน์ l ของทุก word บวก sum
ที่ result[l]: ตรวจสอบ sum%10 ตรงหรือแมปใหม่ได้
Carry = sum/10 ไปคอลัมน์ถัดไป

การทำงานของโค้ด

#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;
            if(solve(idx+1, l, sum+i)) return true;
            i2c[i] = -1; c2i[w[idx][l]-'A'] = -1;
        }
        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(auto& s : words) {
            if(s.size() > result.size()) return false;
            reverse(s.begin(), s.end());
        }
        r = result; w = words;
        return solve(0, 0, 0);
    }
};

int main() {
    Solution ob;
    vector<string> v = {"SEND","MORE"};
    cout << ob.isSolvable(v, "MONEY");
    return 0;
}

อินพุต