求以字母串表示的数字总和

Question

str我在范围内有一串小写字母[a-z]。字符串中的几个字母组合在一起时代表一个数字，[0-9]即“零”= 0、“一”= 1、“二”= 2 等等。

字符串中的字符混乱。但是，保证字符串中的所有字符都可以用来组成一组数字。有些数字也可以重复。不存在a、p等无效字符q。

我的任务是求 所代表的数字之和str。

示例 :
str= "oneeno" 应输出2 (1+1)
str= "onewtofoursevne" 应输出14 (1+2+4+7)

让solve(s)表示求解 的特定子串str。
我有一个字符串数组，v用于存储数字的拼写。v = {“零”，“一”，“二”，...“九”}；

s只要我能找到代表数字的一组字符，我就会分解并添加数字值。

if (contains(s, v[i]) == true)
    dp[s-v[i]] = i + solve(s-v[i])

s-v[i]v[i]表示从 中删除的字符集s。由于不可能以这种方式减去字符串，因此我s-v[i]用change(s, v[i])（在我的代码中）替换。

这看起来像是一个具有多个重复子状态的递归函数。
例如 ：solve(s - v[1] - v[4] - v[7]) = solve(s - v[4] - v[1] - v[7])。

我为此使用了自上而下的动态编程，其中表示的字符 被从中删除时dp[s-v[i]]的状态。我没有删除字符，而是简单地将使用的字符替换为符号。如果整个字符串都有该字符，则意味着我们找到了有效的解决方案（构成基本情况）。sv[i]$$

由于字符串混乱，我使用字符串映射来存储子状态，并且字符串始终进行排序以防止任何冗余。

#include <bits/stdc++.h>
using namespace std;
using ll =  long long;

vector<string> v = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
map<string, int> dp;
bool b;

bool check(string str, int n) {
    string t = v[n];
    sort(t.begin(), t.end()); sort(str.begin(), str.end());
    
    int i=0, j=0, k=0;
    while(i < t.size() && j < str.size()) {
        if(t[i] == str[j]) {
            ++i; ++j; ++k;
        }
        else ++j;
    }
    
    return (k == t.size()) ? true : false;   
}

string change(string str, int n) {
    string t = v[n];
    sort(t.begin(), t.end());
    sort(str.begin(), str.end());
    
    int i=0, j=0;
    while(i < t.size() && j < str.size()) {
        if(t[i] == str[j]) {
            str[j] = '$';
            ++i; ++j;
        }
        else ++j;
    }
    sort(str.begin(), str.end());
    return str;
}

int solve(string str, map<string, int>& dp) {
    
    if(str[str.size()-1] == '$') {
        b = true; // a solution exists
        return 0;
    }

    if(dp.find(str) != dp.end()) // if state is already computed
        return dp[str];
    
    for(int i=0; i<10; i++) {
        if(check(str, i)) {
            return dp[change(str, i)] = i + solve(change(str, i), dp);
        }
    }
    
    return dp[str] = 0;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    #ifndef ONLINE_JUDGE
        freopen("input", "r", stdin);
        freopen("output", "w", stdout);
    #endif
    
    string str; cin >> str;
    sort(str.begin(), str.end());
    
    b = false; 
    
    int res = 0;
    
    for(int i=0; i<10; i++) {
        if(check(str, i)) {
            dp[change(str, i)] = i + solve(change(str, i), dp);
        }
        if(b) { // valid solution found
            res = dp[change(str, i)];
            break; 
        }
    }
    
    cout << res;    
    return 0;
}

该代码对于较小的字符串可以正常工作：
示例：str = "towsnveefourfive"yields18 (2 + 7 + 4 + 5)
但是，对于较大的字符串，例如str = "towsnveefourfiveone"yields0而不是19

我的方法可能有什么错误？

Answer 1

解决这个问题最简单、最快的方法是编写方程式，将某些字母的出现次数与某些数字的出现次数联系起来。然后，您可以计算这些字母的出现次数，并通过高斯消元法求解数字的出现次数。

您需要求解 10 个数字，因此需要 10 个独立方程。我们将从简单的开始：

X = 6s
Z = 0s
W = 2s
G = 8s

“六”是唯一有 x 的数字，因此 x 的数量等于 6 的数量。对于“零”和 zs 以及其他此处的情况也是如此。

然后是一些更复杂的：

O = 1s + 2s + 4s
H = 3s + 8s
F = 4s + 5s
V = 5s + 7s
S = 6s + 7s
I = 5s + 6s + 8s + 9s

求解，我们得到：

0s = Z
1s = O - W - F + V - S + X
2s = W
3s = H - G
4s = F - V + S - X
5s = V - S + X
6s = X
7s = S - X
8s = G
9s = I - G - X - V + S - X