golang 解法, 执行用时: 4 ms, 内存消耗: 2 MB, 提交时间: 2023-09-19 10:13:22

type Weight struct {
	Char   string
	Weight int
}

func isSolvable(words []string, result string) bool {
	// 字母和权重的映射关系 / 因为数值不能0打头故而不能为0的字母
	weightMap, noneZeroChars := make(map[string]int), make(map[string]bool)
	for _, word := range words {
		lw := len(word)
		// 字母因为在数字最前面，所以不能为0
		if lw >= 2 {
			noneZeroChars[string(word[0])] = true
		}
		for i := lw - 1; i >= 0; i-- {
			weightMap[string(word[i])] += int(math.Pow(float64(10), float64(lw-1-i)))
		}
	}
	lr := len(result)
	// 字母因为在数字最前面，所以不能为0
	if lr >= 2 {
		noneZeroChars[string(result[0])] = true
	}
	for i := lr - 1; i >= 0; i-- {
		weightMap[string(result[i])] -= int(math.Pow(float64(10), float64(lr-1-i)))
	}
	var weight []Weight
	for k, v := range weightMap {
		weight = append(weight, Weight{k, v})
	}
	// 按照权值重大到小排序
	sort.Slice(weight, func(i, j int) bool {
		return math.Abs(float64(weight[i].Weight)) > math.Abs(float64(weight[j].Weight))
	})
	digitUsed := make(map[int]bool)
	return backTrack(weight, digitUsed, noneZeroChars, 0, 0)
}

func backTrack(weight []Weight, digitUsed map[int]bool, noneZeroChars map[string]bool, pos, sum int) bool {
	if pos == len(weight) {
		return sum == 0
	}
	// 组装除去当前项后剩余项最大最小值
	maxRight, maxLft, minRight, minLeft, max, min := 9, 0, 9, 0, sum, sum
	for i := pos + 1; i < len(weight); i++ {
		weight := weight[i].Weight
		if weight > 0 {
			max += maxRight * weight
			min += minLeft * weight
			maxRight--
			minLeft++
		} else {
			max += maxLft * weight
			min += minRight * weight
			maxLft++
			minRight--
		}
	}
	// 求当前数字的上下限
	left, right := 0, 9
	if weight[pos].Weight < 0 {
		left, right = -min/weight[pos].Weight, -max/weight[pos].Weight
	} else if weight[pos].Weight > 0 {
		left, right = -max/weight[pos].Weight, -min/weight[pos].Weight
	}
	left = int(math.Max(float64(left), 0))
	right = int(math.Min(float64(right), 9))
	for i := left; i <= right; i++ {
		if digitUsed[i] {
			continue
		}
		// 部分字母因为在数字最前面，所以不能为0
		if noneZeroChars[weight[pos].Char] && i == 0 {
			continue
		}
		digitUsed[i] = true
		add := i * weight[pos].Weight
		if backTrack(weight, digitUsed, noneZeroChars, pos+1, sum+add) {
			return true
		}
		digitUsed[i] = false
	}
	return false
}

java 解法, 执行用时: 1 ms, 内存消耗: 39 MB, 提交时间: 2023-09-19 10:12:24

import java.util.Arrays;
import java.util.HashSet;

class Solution {
    public static void main(String[] args) {
        boolean res = new Solution().isSolvable(new String[]{"SIX", "SEVEN", "SEVEN"}, "TWENTY");
        System.out.println(res);
    }

    public boolean isSolvable(String[] words, String result) {
        HashSet<Character> set = new HashSet<>();
        for (String word : words) {
            for (int i = 0; i < word.length(); i++) {
                set.add(word.charAt(i));
            }
        }

        for (int i = 0; i < result.length(); i++) {
            set.add(result.charAt(i));
        }

        if (set.size() > 10) {
            return false;
        }


        int[][] coefficient = new int[26][3];

        for (String word : words) {
            int x = 1;
            for (int j = word.length() - 1; j >= 0; j--) {
                coefficient[word.charAt(j) - 'A'][0] += x;
                x *= 10;
            }
            if (word.length() > 1) {
                coefficient[word.charAt(0) - 'A'][1] = 1;
            }
        }

        int x = 1;
        for (int i = result.length() - 1; i >= 0; i--) {
            coefficient[result.charAt(i) - 'A'][0] -= x;
            x *= 10;
        }

        if (result.length() > 1) {
            coefficient[result.charAt(0) - 'A'][1] = 1;
        }

        int[][] filtered = new int[set.size()][4];
        int i = 0;
        for (int[] item : coefficient) {
            if (item[0] != 0 || item[1] != 0) {
                filtered[i][0] = item[0];
                filtered[i++][1] = item[1];
            }
        }

        Arrays.sort(filtered, (a, b) -> {
            return Math.abs(b[0]) - Math.abs(a[0]);
        });


        int min = 0;
        int max = 0;

        for (int k = filtered.length - 1; k >= 0; k--) {
            if (filtered[k][0] > 0) {
                filtered[k][2] = max;
                filtered[k][3] = min;
                max += 9 * filtered[k][0];
            } else {
                filtered[k][2] = max;
                filtered[k][3] = min;
                min += 9 * filtered[k][0];
            }
        }

        return buckTrace(new boolean[10], 0, filtered, 0);
    }


    /**
     *
     * @param bucket  当前可供选择的数字
     * @param used    已确定了值的变量数量， 即当前需要确定X[used]的值
     * @param coefficient  系数
     * @param preSum    A0X0 + A1X1 + A[used-1]X[used-1] 的值
     * @return
     */
    private boolean buckTrace(boolean[] bucket, int used, int[][] coefficient, int preSum) {

        if (used == bucket.length) {
            return preSum == 0;
        }

        for (int i = 0; i < bucket.length; i++) {

            if (!bucket[i]) {
                if (used < coefficient.length) {

                    // case X不能为0
                    if (coefficient[used][1] == 1 && i == 0) {
                        continue;
                    }

                    // case X=i 不满足要求
                    int max = coefficient[used][2];
                    int min = coefficient[used][3];
                    int test = i * coefficient[used][0];
                    if (test + preSum + max < 0 || test + preSum + min > 0) {
                        continue;
                    }
                }

                // 标记i已被使用 , X选择了i
                bucket[i] = true;
                // 计算下一个前缀和，不能改变preSum的值， 因为在评估其他的i值，还需要用
                int nextPreSum = used < coefficient.length ? preSum + i * coefficient[used][0] : preSum;
                if (buckTrace(bucket, used + 1, coefficient, nextPreSum)) {
                    return true;
                }
                // 撤销选择
                bucket[i] = false;
            }
        }

        return false;
    }

}

python3 解法, 执行用时: 232 ms, 内存消耗: 16.2 MB, 提交时间: 2023-09-19 10:10:44

'''
以words=["SEND","MORE"],result = "MONEY"参考为例
先将字符转换为方程1000S+100E+10N+D+1000M+100O+10R+E = 10000M+1000O+100N+10E+Y
合并同类项按照系数的绝对值大小排序为-9000M+1000S-900O+91E-90N+10R+D-Y = 0
从前往后深搜字符的映射值，并根据后续项的最大最小值进行剪枝
如遍历到M时，此时的系数若>=2则后续项不能提供正向的9000*2抵消使得和为0明显不满足要求
确认前导零时要注意字符的方程项系数为0的情况
'''
from collections import defaultdict


class Solution:
    def isSolvable(self, words, result: str) -> bool:
        # 边界情况绝对无解
        if all(len(word)+1 < len(result) for word in words):
            return False
        # 建立方程
        dct = defaultdict(int)
        for word in words:
            k = len(word)
            for i in range(k):
                dct[word[i]] += 10**(k-i-1)
        n = len(result)
        for i in range(n):
            dct[result[i]] -= 10 ** (n - i - 1)
        # 按照系数的绝对值大小进行逆排序并去掉零系数的项
        lst = [[dct[k], k] for k in dct if dct[k]]
        lst.sort(key=lambda x: abs(x[0]), reverse=True)
        m = len(lst)

        # 计算剩余序列的最大值与最小值
        def compute_ceil_floor(rest, pos, neg):
            post_ceil = 0
            for r in range(len(neg)):
                post_ceil += rest[r]*neg[r]
            for r in range(len(pos)):
                post_ceil += rest[-r-1]*pos[r]
            post_floor = 0
            for r in range(len(pos)):
                post_floor += rest[r]*pos[r]
            for r in range(len(neg)):
                post_floor += rest[-r-1]*neg[r]
            return post_ceil, post_floor

        # 检查该映射是否存在前导零
        def check():
            map_num = dict()
            for c in range(m):
                map_num[lst[c][1]] = mapping[c]
            for word in words+[result]:
                if len(word) >= 2:
                    # 映射为前导零
                    if word[0] in map_num and map_num[word[0]] == 0:
                        return False
                    # 首字母方程系数为0可选任意剩余值若剩余为0则不符合
                    if word[0] not in map_num and m == 9 and 0 not in mapping:
                        return False
            return True

        # 深搜寻找可能的映射
        ans = []
        mapping = [-1]*m

        def dfs(pre_sum, ind):
            nonlocal ans
            # 搜寻到存在的解就停止
            if ans:
                return
            if ind == m:
                if not pre_sum and check():
                    ans = mapping[:]
                return
            for num in range(10):
                if num not in mapping:
                    # 计算选定当前值的情况下后续可能的最大最小值是否还能满足和为0
                    rest = [j for j in range(10) if j not in mapping and j!=num]
                    rest.sort()
                    pos = [ls[0] for ls in lst[ind+1:] if ls[0] > 0]
                    neg = [ls[0] for ls in lst[ind+1:] if ls[0] < 0]
                    post_ceil, post_floor = compute_ceil_floor(rest, pos, neg)
                    # 剪枝
                    if -post_ceil <= pre_sum + lst[ind][0] * num <= -post_floor:
                        mapping[ind] = num
                        dfs(pre_sum + lst[ind][0]*num, ind+1)
                        # 回溯
                        mapping[ind] = -1

        dfs(0, 0)
        return True if ans else False

cpp 解法, 执行用时: 4 ms, 内存消耗: 7.3 MB, 提交时间: 2023-09-19 10:09:27

using PCI = pair<char, int>;

class Solution {
private:
    vector<PCI> weight;
    vector<int> suffix_sum_min, suffix_sum_max;
    vector<int> lead_zero;
    bool used[10];

public:
    int pow10(int x) {
        int ret = 1;
        for (int i = 0; i < x; ++i) {
            ret *= 10;
        }
        return ret;
    }

    bool dfs(int pos, int total) {
        if (pos == weight.size()) {
            return total == 0;
        }
        if (!(total + suffix_sum_min[pos] <= 0 && 0 <= total + suffix_sum_max[pos])) {
            return false;
        }
        for (int i = lead_zero[pos]; i < 10; ++i) {
            if (!used[i]) {
                used[i] = true;
                bool check = dfs(pos + 1, total + weight[pos].second * i);
                used[i] = false;
                if (check) {
                    return true;
                }
            }
        }
        return false;
    }

    bool isSolvable(vector<string>& words, string result) {
        unordered_map<char, int> _weight;
        unordered_set<char> _lead_zero;
        for (const string& word: words) {
            for (int i = 0; i < word.size(); ++i) {
                _weight[word[i]] += pow10(word.size() - i - 1);
            }
            if (word.size() > 1) {
                _lead_zero.insert(word[0]);
            }
        }
        for (int i = 0; i < result.size(); ++i) {
            _weight[result[i]] -= pow10(result.size() - i - 1);
        }
        if (result.size() > 1) {
            _lead_zero.insert(result[0]);
        }

        weight = vector<PCI>(_weight.begin(), _weight.end());
        sort(weight.begin(), weight.end(), [](const PCI& u, const PCI& v) {
            return abs(u.second) > abs(v.second);
        });
        int n = weight.size();
        suffix_sum_min.resize(n);
        suffix_sum_max.resize(n);
        for (int i = 0; i < n; ++i) {
            vector<int> suffix_pos, suffix_neg;
            for (int j = i; j < n; ++j) {
                if (weight[j].second > 0) {
                    suffix_pos.push_back(weight[j].second);
                }
                else if (weight[j].second < 0) {
                    suffix_neg.push_back(weight[j].second);
                }
                sort(suffix_pos.begin(), suffix_pos.end());
                sort(suffix_neg.begin(), suffix_neg.end());
            }
            for (int j = 0; j < suffix_pos.size(); ++j) {
                suffix_sum_min[i] += (suffix_pos.size() - 1 - j) * suffix_pos[j];
                suffix_sum_max[i] += (10 - suffix_pos.size() + j) * suffix_pos[j];
            }
            for (int j = 0; j < suffix_neg.size(); ++j) {
                suffix_sum_min[i] += (9 - j) * suffix_neg[j];
                suffix_sum_max[i] += j * suffix_neg[j];
            }
        }

        lead_zero.resize(n);
        for (int i = 0; i < n; ++i) {
            lead_zero[i] = (_lead_zero.count(weight[i].first) ? 1 : 0);
        }
        
        memset(used, false, sizeof(used));
        return dfs(0, 0);
    }
};

python3 解法, 执行用时: 64 ms, 内存消耗: 16 MB, 提交时间: 2023-09-19 10:08:46

'''
权值合并

SEND  =             S * 1000 + E * 100 + N * 10 + D
MORE  =             M * 1000 + O * 100 + R * 10 + E
MONEY = M * 10000 + O * 1000 + N * 100 + E * 10 + Y

S * 1000 + E * 91 - N * 90 + D - M * 9000 - O * 900 + R * 10 - Y = 0
系数为正：S * 1000 + E * 91 + R * 10 + D
系数为负：-(O * 900 + N * 90 + Y)
'''

class Solution:
    def isSolvable(self, words: List[str], result: str) -> bool:
        _weight = dict()
        _lead_zero = set()
        for word in words:
            for i, ch in enumerate(word[::-1]):
                _weight[ch] = _weight.get(ch, 0) + 10**i
            if len(word) > 1:
                _lead_zero.add(word[0])
        for i, ch in enumerate(result[::-1]):
            _weight[ch] = _weight.get(ch, 0) - 10**i
        if len(result) > 1:
            _lead_zero.add(result[0])
        
        weight = sorted(list(_weight.items()), key=lambda x: -abs(x[1]))
        suffix_sum_min = [0] * len(weight)
        suffix_sum_max = [0] * len(weight)
        for i in range(len(weight)):
            suffix_pos = sorted(x[1] for x in weight[i:] if x[1] > 0)
            suffix_neg = sorted(x[1] for x in weight[i:] if x[1] < 0)
            suffix_sum_min[i] = sum((len(suffix_pos) - 1 - j) * elem for j, elem in enumerate(suffix_pos)) + sum((9 - j) * elem for j, elem in enumerate(suffix_neg))
            suffix_sum_max[i] = sum((10 - len(suffix_pos) + j) * elem for j, elem in enumerate(suffix_pos)) + sum(j * elem for j, elem in enumerate(suffix_neg))
        
        lead_zero = [int(ch in _lead_zero) for (ch, _) in weight]
        used = [0] * 10
        
        def dfs(pos, total):
            if pos == len(weight):
                return total == 0
            if not total + suffix_sum_min[pos] <= 0 <= total + suffix_sum_max[pos]:
                return False
            for i in range(lead_zero[pos], 10):
                if not used[i]:
                    used[i] = True
                    check = dfs(pos + 1, total + weight[pos][1] * i)
                    used[i] = False
                    if check:
                        return True
            return False
        
        return dfs(0, 0)

python3 解法, 执行用时: 452 ms, 内存消耗: 15.9 MB, 提交时间: 2023-09-19 10:02:36

class Solution:
    def isSolvable(self, words: List[str], result: str) -> bool:
        used, carry = [False] * 10, [0] * 10
        lead_zero, rep = dict(), dict()

        for word in words:
            if len(word) > len(result):
                return False
            for ch in word:
                rep[ch] = -1
                lead_zero[ch] = max(lead_zero.get(ch, 0), 0)
            if len(word) > 1:
                lead_zero[word[0]] = 1
        for ch in result:
            rep[ch] = -1
            lead_zero[ch] = max(lead_zero.get(ch, 0), 0)
        if len(result) > 1:
            lead_zero[result[0]] = 1
        
        def dfs(pos, iden, length):
            if pos == length:
                return carry[pos] == 0
            elif iden < len(words):
                sz = len(words[iden])
                if sz < pos or rep[words[iden][sz - pos - 1]] != -1:
                    return dfs(pos, iden + 1, length)
                else:
                    ch = words[iden][sz - pos - 1]
                    for i in range(lead_zero[ch], 10):
                        if not used[i]:
                            used[i], rep[ch] = True, i
                            check = dfs(pos, iden + 1, length)
                            used[i], rep[ch] = False, -1
                            if check:
                                return True
                    return False
            else:
                left = carry[pos] + sum(rep[word[len(word) - pos - 1]] for word in words if len(word) > pos)
                carry[pos + 1], left = left // 10, left % 10
                ch = result[len(result) - pos - 1]
                if rep[ch] == left:
                    return dfs(pos + 1, 0, length)
                elif rep[ch] == -1 and not used[left] and not (lead_zero[ch] == 1 and left == 0):
                    used[left], rep[ch] = True, left
                    check = dfs(pos + 1, 0, length)
                    used[left], rep[ch] = False, -1
                    return check
                else:
                    return False

        return dfs(0, 0, len(result))