{"id":7519,"date":"2026-07-27T23:26:37","date_gmt":"2026-07-27T15:26:37","guid":{"rendered":"https:\/\/i007.cc\/wordpress\/?p=7519"},"modified":"2026-07-27T23:26:37","modified_gmt":"2026-07-27T15:26:37","slug":"%e7%94%a8c%e8%ae%b2%e8%ae%b2-leetcode-1307-%e7%9a%84%e6%9c%80%e4%bd%b3%e6%80%9d%e8%b7%af","status":"publish","type":"post","link":"https:\/\/i007.cc\/wordpress\/archives\/7519","title":{"rendered":"\u7528C++\u8bb2\u8bb2 LeetCode 1307 \u7684\u6700\u4f73\u601d\u8def"},"content":{"rendered":"
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n
\n
\n
\n
\n
\n
\n

LeetCode 1307\u300cVerbal Arithmetic Puzzle\u300d\uff08\u6587\u5b57\u7b97\u5f0f\uff09\u662f\u4e00\u9053 Hard \u9898\uff0c\u672c\u8d28\u662f\u7ea6\u675f\u6ee1\u8db3\u95ee\u9898\uff1a\u7ed9\u4e00\u7ec4\u5355\u8bcd\u8868\u793a\u7684\u52a0\u6cd5\u7b49\u5f0f\uff08\u6bd4\u5982 “SEND” + “MORE” == “MONEY”\uff09\uff0c\u8981\u7ed9\u6bcf\u4e2a\u4e0d\u540c\u7684\u5b57\u6bcd\u5206\u914d\u4e00\u4e2a 0-9 \u7684\u6570\u5b57\uff08\u540c\u4e00\u5b57\u6bcd\u540c\u4e00\u4e2a\u6570\u5b57\uff0c\u4e0d\u540c\u5b57\u6bcd\u4e0d\u540c\u6570\u5b57\uff0c\u591a\u4f4d\u6570\u7684\u9996\u5b57\u6bcd\u4e0d\u80fd\u662f 0\uff09\uff0c\u5224\u65ad\u662f\u5426\u5b58\u5728\u5408\u6cd5\u5206\u914d\u8ba9\u7b49\u5f0f\u6210\u7acb\u3002\u6700\u6734\u7d20\u7684\u60f3\u6cd5\u662f\u66b4\u529b\u679a\u4e3e\u5b57\u6bcd\u5230\u6570\u5b57\u7684\u6392\u5217\uff08\u6700\u591a 10 \u4e2a\u4e0d\u540c\u5b57\u6bcd\uff0c10! \u7ea6 362 \u4e07\u79cd\u6392\u5217\uff09\uff0c\u4f46\u66f4\u597d\u7684\u601d\u8def\u662f\u628a\u95ee\u9898\u8f6c\u5316\u6210\u4e00\u4e2a\u300c\u7ebf\u6027\u65b9\u7a0b\u300d\uff0c\u518d\u7528\u56de\u6eaf\u914d\u5408\u6570\u503c\u526a\u679d\uff0c\u8fd9\u6837\u80fd\u628a\u641c\u7d22\u7a7a\u95f4\u780d\u6389\u7edd\u5927\u90e8\u5206\u3002<\/p>\n

\u5173\u952e\u7684\u8f6c\u5316\u70b9\u5728\u4e8e\uff1a\u7b49\u5f0f\u4e24\u8fb9\u53ef\u4ee5\u5408\u5e76\u6210\u4e00\u4e2a\u5173\u4e8e\u5b57\u6bcd\u7cfb\u6570\u7684\u7ebf\u6027\u7ec4\u5408\u3002\u6bd4\u5982\u67d0\u4e2a\u5b57\u6bcd\u5728\u52a0\u6570\u91cc\u7684\u7b2c k \u4f4d\uff08\u4ece\u53f3\u5f80\u5de6\uff0c\u4e2a\u4f4d\u662f\u7b2c 0 \u4f4d\uff09\u51fa\u73b0\uff0c\u5c31\u7ed9\u5b83\u7684\u7cfb\u6570\u52a0\u4e0a 10^k\uff1b\u5982\u679c\u8fd9\u4e2a\u5b57\u6bcd\u51fa\u73b0\u5728\u7ed3\u679c\uff08\u7b49\u53f7\u53f3\u8fb9\uff09\u7684\u7b2c k \u4f4d\uff0c\u5c31\u7ed9\u5b83\u7684\u7cfb\u6570\u51cf\u53bb 10^k\u3002\u8fd9\u6837\u6574\u4e2a\u7b49\u5f0f “SEND + MORE = MONEY” \u5c31\u53d8\u6210\u4e86 sum(coeff[letter] * digit[letter]) == 0 \u8fd9\u4e00\u4e2a\u65b9\u7a0b\uff0c\u95ee\u9898\u8f6c\u5316\u4e3a\u300c\u7ed9\u6bcf\u4e2a\u5b57\u6bcd\u5206\u914d\u4e0d\u540c\u6570\u5b57\uff0c\u4f7f\u8fd9\u4e2a\u52a0\u6743\u548c\u4e3a 0\u300d\uff0c\u8fd9\u6837\u5c31\u4e0d\u7528\u5173\u5fc3\u5177\u4f53\u662f\u54ea\u4e2a\u5355\u8bcd\u7684\u54ea\u4e00\u4f4d\u4e86\uff0c\u7edf\u4e00\u53d8\u6210\u4e00\u4e2a\u6570\u503c\u7ea6\u675f\u95ee\u9898\u3002<\/p>\n

\n
\n
<\/div>\n<\/div>\n
cpp<\/div>\n
\n
class Solution {\r\npublic:\r\n    bool isSolvable(vector<string>& words, string result) {\r\n        vector<int> coeff(26, 0);\r\n        vector<bool> nonZero(26, false); \/\/ \u591a\u4f4d\u6570\u7684\u9996\u5b57\u6bcd\u4e0d\u80fd\u53d6 0\r\n\r\n        auto addWord = [&](const string& w, int sign) {\r\n            int p = 1;\r\n            for (int i = (int)w.size() - 1; i >= 0; --i) {\r\n                coeff[w[i] - 'A'] += sign * p;\r\n                p *= 10;\r\n            }\r\n            if (w.size() > 1) nonZero[w[0] - 'A'] = true;\r\n        };\r\n\r\n        for (auto& w : words) addWord(w, 1);\r\n        addWord(result, -1); \/\/ \u7ed3\u679c\u8fd9\u8fb9\u7b26\u53f7\u53d6\u53cd\r\n\r\n        vector<int> letters;\r\n        for (int c = 0; c < 26; ++c) if (coeff[c] != 0) letters.push_back(c);\r\n        if (letters.size() > 10) return false; \/\/ \u5b57\u6bcd\u79cd\u7c7b\u8d85\u8fc7 10 \u4e2a\uff0c\u65e0\u89e3\r\n\r\n        \/\/ \u7cfb\u6570\u7edd\u5bf9\u503c\u5927\u7684\u5b57\u6bcd\u5148\u5206\u914d\uff0c\u526a\u679d\u6548\u679c\u66f4\u597d\r\n        sort(letters.begin(), letters.end(), [&](int a, int b) {\r\n            return abs(coeff[a]) > abs(coeff[b]);\r\n        });\r\n\r\n        int m = letters.size();\r\n        vector<long long> suffixMaxAbs(m + 1, 0); \/\/ \u540e\u7f00\u7cfb\u6570\u7edd\u5bf9\u503c\u4e4b\u548c\u7684\u4e0a\u754c\r\n        for (int i = m - 1; i >= 0; --i)\r\n            suffixMaxAbs[i] = suffixMaxAbs[i + 1] + (long long)abs(coeff[letters[i]]) * 9;\r\n\r\n        vector<bool> usedDigit(10, false);\r\n\r\n        function<bool(int, long long)> dfs = [&](int idx, long long curSum) -> bool {\r\n            if (idx == m) return curSum == 0;\r\n            if (llabs(curSum) > suffixMaxAbs[idx]) return false; \/\/ \u5269\u4e0b\u7684\u5b57\u6bcd\u65e0\u8bba\u600e\u4e48\u53d6\u90fd\u62c9\u4e0d\u56de 0\uff0c\u526a\u679d\r\n\r\n            int letter = letters[idx];\r\n            for (int d = 0; d <= 9; ++d) {\r\n                if (usedDigit[d]) continue;\r\n                if (d == 0 && nonZero[letter]) continue;\r\n                usedDigit[d] = true;\r\n                if (dfs(idx + 1, curSum + (long long)coeff[letter] * d)) {\r\n                    usedDigit[d] = false;\r\n                    return true;\r\n                }\r\n                usedDigit[d] = false;\r\n            }\r\n            return false;\r\n        };\r\n\r\n        return dfs(0, 0);\r\n    }\r\n};<\/pre>\n
 <\/p>\n<\/div>\n<\/div>\n
\u8fd9\u4e2a\u89e3\u6cd5\u6709\u4e24\u4e2a\u5173\u952e\u7684\u4f18\u5316\u70b9\u503c\u5f97\u5c55\u5f00\u8bb2\u3002\u7b2c\u4e00\u662f\u628a\u95ee\u9898\u4ece\u300c\u6309\u5355\u8bcd\u3001\u6309\u4f4d\u7f6e\u300d\u7684\u590d\u6742\u7ed3\u6784\uff0c\u538b\u7f29\u6210\u300c\u6bcf\u4e2a\u5b57\u6bcd\u4e00\u4e2a\u7cfb\u6570\u300d\u7684\u4e00\u7ef4\u7ebf\u6027\u65b9\u7a0b\uff0c\u8fd9\u4e00\u6b65\u8f6c\u5316\u4e4b\u540e\u56de\u6eaf\u53ea\u9700\u8981\u5904\u7406\u6700\u591a 10 \u4e2a\u5b57\u6bcd\uff0c\u903b\u8f91\u53d8\u5f97\u975e\u5e38\u5e72\u51c0\uff0c\u4e0d\u7528\u5728 DFS \u91cc\u540c\u65f6\u8ffd\u8e2a\u6bcf\u4e00\u4f4d\u7684\u8fdb\u4f4d\u3002\u7b2c\u4e8c\u662f\u526a\u679d\uff1a\u7ed9\u5b57\u6bcd\u6309\u7cfb\u6570\u7edd\u5bf9\u503c\u4ece\u5927\u5230\u5c0f\u6392\u5e8f\u540e\u4f18\u5148\u5206\u914d\uff0c\u8fd9\u6837\u9519\u8bef\u7684\u5206\u914d\u80fd\u66f4\u65e9\u88ab\u53d1\u73b0\uff08\u7cfb\u6570\u5927\u7684\u5b57\u6bcd\u5bf9\u603b\u548c\u5f71\u54cd\u4e5f\u5927\uff0c\u65e9\u70b9\u5b9a\u4e0b\u6765\u80fd\u66f4\u5feb\u5224\u65ad\u67d0\u6761\u5206\u652f\u8d70\u4e0d\u901a\uff09\uff1b\u540c\u65f6\u7528 suffixMaxAbs \u9884\u8ba1\u7b97\u300c\u5269\u4f59\u672a\u5206\u914d\u5b57\u6bcd\u65e0\u8bba\u600e\u4e48\u53d6\uff0c\u52a0\u6743\u548c\u7684\u7edd\u5bf9\u503c\u4e0a\u9650\u662f\u591a\u5c11\u300d\uff0c\u5982\u679c\u5f53\u524d\u7d2f\u79ef\u548c\u7684\u7edd\u5bf9\u503c\u5df2\u7ecf\u8d85\u8fc7\u8fd9\u4e2a\u4e0a\u9650\uff0c\u8bf4\u660e\u5269\u4e0b\u7684\u5b57\u6bcd\u65e0\u8bba\u600e\u4e48\u5206\u914d\u90fd\u4e0d\u53ef\u80fd\u628a\u603b\u548c\u62c9\u56de 0\uff0c\u76f4\u63a5\u526a\u6389\u8fd9\u6761\u5206\u652f\uff0c\u4e0d\u7528\u7ee7\u7eed\u5f80\u4e0b\u641c\u3002<\/p>\n
\u590d\u6742\u5ea6\u4e0a\uff0c\u6700\u574f\u60c5\u51b5\u4e0b\u4ecd\u7136\u662f\u6307\u6570\u7ea7\u7684\uff08\u6700\u591a 10 \u4e2a\u5b57\u6bcd\u5168\u6392\u5217\uff0c\u7ea6 10! \u6b21\u5c1d\u8bd5\uff09\uff0c\u4f46\u56e0\u4e3a\u6709\u7cfb\u6570\u526a\u679d\uff0c\u5b9e\u9645\u8fd0\u884c\u4e2d\u5927\u90e8\u5206\u4e0d\u5408\u6cd5\u7684\u5206\u652f\u4f1a\u5728\u5f88\u6d45\u7684\u6df1\u5ea6\u5c31\u88ab\u526a\u6389\uff0c\u5b9e\u6d4b\u6548\u7387\u6bd4\u6734\u7d20\u7684\u300c\u679a\u4e3e\u5168\u90e8\u6392\u5217\u518d\u9010\u4e2a\u9a8c\u8bc1\u7b49\u5f0f\u300d\u5feb\u5f88\u591a\uff0c\u80fd\u7a33\u5b9a\u901a\u8fc7 LeetCode \u7684\u65f6\u95f4\u9650\u5236\u3002<\/p>\n
\u5982\u679c\u4e0d\u8ffd\u6c42\u6700\u4f18\u53ea\u60f3\u5148\u5199\u4e00\u7248\u80fd\u8fc7\u7684\u66b4\u529b\u89e3\uff0c\u4e5f\u53ef\u4ee5\u76f4\u63a5\u7528 next_permutation \u679a\u4e3e 0-9 \u7684\u6392\u5217\uff0c\u53d6\u524d letters.size() \u4e2a\u6570\u5b57\u4f9d\u6b21\u8d4b\u7ed9\u5b57\u6bcd\uff0c\u518d\u628a\u6bcf\u4e2a\u5355\u8bcd\u6309\u4f4d\u6570\u8fd8\u539f\u6210\u6570\u503c\u9a8c\u8bc1\u7b49\u5f0f\u662f\u5426\u6210\u7acb\uff0c\u8fd9\u79cd\u5199\u6cd5\u66f4\u76f4\u89c2\u597d\u61c2\uff0c\u7f3a\u70b9\u662f\u6ca1\u6709\u526a\u679d\uff0c\u7eaf\u7cb9\u9760\u6392\u5217\u4e2a\u6570\u5c11\uff08\u6700\u591a 10 \u4e2a\u5b57\u6bcd\uff09\u6491\u8fc7\u53bb\uff0c\u4ee3\u7801\u91cf\u66f4\u5c0f\u4f46\u6548\u7387\u660e\u663e\u4e0d\u5982\u4e0a\u9762\u8fd9\u7248\uff0c\u9002\u5408\u5148\u5199\u51fa\u6765\u4fdd\u5e95\u518d\u4f18\u5316\u3002<\/p>\n<\/div>\n<\/div>\n<\/div>\n
\n
<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n
<\/div>\n
\n
\n
\n
\n
<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
<\/div>\n","protected":false},"excerpt":{"rendered":"
LeetCode 1307\u300cVerbal<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","footnotes":""},"categories":[24],"tags":[],"class_list":["post-7519","post","type-post","status-publish","format-standard","hentry","category-value_docs"],"_links":{"self":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7519","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/comments?post=7519"}],"version-history":[{"count":0,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7519\/revisions"}],"wp:attachment":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/media?parent=7519"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/categories?post=7519"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/tags?post=7519"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}