Câu đố số học bằng từ trong C++

Cho phương trình: các từ bên trái cộng nhau = từ kết quả bên phải. Kiểm tra có giải được không với quy tắc: mỗi ký tự ánh xạ 1 chữ số (0-9), ký tự khác nhau → chữ số khác nhau, không số dẫn đầu 0, tổng bên trái = bên phải.

Ví dụ: words=["SEND","MORE"], result="MONEY" → True. Ánh xạ: S→9, E→5, N→6, D→7, M→1, O→0, R→8, Y→2. Khi đó 9567+1085=10652.

Giải pháp

Backtracking cột theo cột (từ phải sang trái) với carry:

• Đảo ngược tất cả từ và result
• Mảng i2c[10]: chữ số → ký tự, c2i[26]: ký tự → chữ số (-1 nếu chưa gán)
• Hàm solve(idx, l, sum): xử lý cột l, từ idx, carry = sum
  • Nếu l == result.length(): trả về sum == 0
  • Nếu idx == words.size(): xử lý chữ số kết quả tại cột l
  • Nếu l ≥ words[idx].length(): chuyển từ tiếp theo
  • Nếu ký tự đã gán: kiểm tra leading zero, cộng vào sum, đệ quy
  • Nếu chưa gán: thử mọi chữ số 0-9 chưa dùng, kiểm tra leading zero, gán, đệ quy, backtrack

Ví dụ mã C++

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

Đầu vào

{"SEND","MORE"}, "MONEY"

Đầu ra

1