『LeetCode』423 从英文中重建数字

题目

423. 从英文中重建数字

给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按升序返回原始的数字。

示例 1：

输入：s = "owoztneoer"
输出："012"

示例 2：

输入：s = "fviefuro"
输出："45"

提示：

1 <= s.length <= 10^{5}
s[i] 为 ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"] 这些字符之一
s 保证是一个符合题目要求的字符串

题解

【从英文重建数字】统计词频解十元一次方程

思路

今天我们来学习下数字的英文表示🤣

因为字符串被打乱了，不管如何我们先统计一次词频

# Code language: Python
class Solution:
    def originalDigits(self, s: str) -> str:
        cnt = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine']
        s = defaultdict(set)
        for num in cnt:
            for c in num:
                s[c].add(num)
        for i, j in s.items():
            print(f'{i} : {j}')
        return ''

输出了这样的结果

z : {'zero'}
e : {'zero', 'nine', 'one', 'eight', 'five', 'three', 'seven'}
r : {'four', 'zero', 'three'}
o : {'four', 'zero', 'two', 'one'}
n : {'nine', 'seven', 'one'}
t : {'eight', 'two', 'three'}
w : {'two'}
h : {'eight', 'three'}
f : {'four', 'five'}
u : {'four'}
i : {'eight', 'nine', 'six', 'five'}
v : {'five', 'seven'}
s : {'six', 'seven'}
x : {'six'}
g : {'eight'}

很惊喜的发现有几个字母只会在一个数字的英文中出现！

z 只在 zero 中出现
w 只在 two 中出现
u 只在 four 中出现
x 只在 six 中出现
g 只在 eight 中出现

所以根据 z, w, u, x, g 四个字母的频次就能确定 0, 2, 4, 6, 8 的出现次数

我们只需要确定 1, 3, 5, 7, 9 的出现次数就能得到答案，我将数字替换掉已经确定的频次的数字，继续观察

z : {0}
e : {0, 'nine', 'one', 8, 'five', 'three', 'seven'}
r : {4, 0, 'three'}
o : {4, 0, 2, 'one'}
n : {'nine', 'seven', 'one'}
t : {8, 2, 'three'}
w : {2}
h : {8, 'three'}
f : {4, 'five'}
u : {4}
i : {8, 'nine', 6, 'five'}
v : {'five', 'seven'}
s : {6, 'seven'}
x : {6}
g : {8}

容易发现：

根据 o 可以确定 1
根据 t 或 h 可以确定 3
根据 f 可以确定 5
根据 s 可以确定 7

好的，最后我们只剩下 9 还没确定了，但这不难，因为其他所有数字都已经确定频次了，所以只需任意找 n, i, e 中的一个就能确定 9 (不过需要注意的是 n 在 three, seven, nine 中出现了两次)

最后根据结果敲出代码就行

# Code language: Python
class Solution:
    def originalDigits(self, s: str) -> str:
        c = Counter(s)
        n0, n2, n4, n6, n8 = c['z'], c['w'], c['u'], c['x'], c['g']
        n1, n3, n5, n7 = c['o'] - n4 - n0 - n2, c['h'] - n8, c['f'] - n4, c['s'] - n6
        n9 = c['i'] - n5 - n6 - n8
        return "".join(i * j for i, j in zip('0123456789', [n0, n1, n2, n3, n4, n5, n6, n7, n8, n9]))

// Code language: Java
class Solution {
    public String originalDigits(String s) {
        int[] num = new int[10], cnt = new int[26];
        for (char ss: s.toCharArray()) {
            cnt[ss - 'a']++;
        }
        num[0] = cnt['z' - 'a'];
        num[2] = cnt['w' - 'a'];
        num[4] = cnt['u' - 'a'];
        num[6] = cnt['x' - 'a'];
        num[8] = cnt['g' - 'a'];
        num[1] = cnt['o' - 'a'] - num[4] - num[0] - num[2];
        num[3] = cnt['h' - 'a'] - num[8];
        num[5] = cnt['f' - 'a'] - num[4];
        num[7] = cnt['s' - 'a'] - num[6];
        num[9] = cnt['i' - 'a'] - num[5] - num[6] - num[8];
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 10; ++i) {
            char x = (char)('0' + i);
            for (int j = 0; j < num[i]; ++j) {
                sb.append(x);
            }
        }
        return sb.toString();
    }
}

// Code language: C++
class Solution {
public:
    string originalDigits(string s) {
        int num[10];
        int cnt[26];
        memset(cnt, 0, sizeof(cnt));
        memset(num, 0, sizeof(num));
        for (char ss: s) {
            cnt[ss - 'a']++;
        }
        num[0] = cnt['z' - 'a'];
        num[2] = cnt['w' - 'a'];
        num[4] = cnt['u' - 'a'];
        num[6] = cnt['x' - 'a'];
        num[8] = cnt['g' - 'a'];
        num[1] = cnt['o' - 'a'] - num[4] - num[0] - num[2];
        num[3] = cnt['h' - 'a'] - num[8];
        num[5] = cnt['f' - 'a'] - num[4];
        num[7] = cnt['s' - 'a'] - num[6];
        num[9] = cnt['i' - 'a'] - num[5] - num[6] - num[8];
        stringstream ss;
        for (int i = 0; i < 10; ++i) {
            for (int j = 0; j < num[i]; ++j) {
                ss << i;
            }
        }
        string ans;
        ss >> ans;
        return ans;
    }
};

时间复杂度：\(O(n)\)
空间复杂度：\(O(1)\)

方程组解法

再补充一个方程组解法，不然显得有点文不对题🤣

实际上这是一个十元一次的方程组，可以写成矩阵形式 \(Ax=b\)，有解唯一解的充要条件是系数矩阵 \(A\) 的秩等于增广矩阵 \(A|B\) 的秩且等于未知数个数 \(10\) （本题是符合的），如果有解那只要解出这个线性方程组即可
PS: \(A\) 的行表示数字的英文表示中各个字母的词频，\(b\) 是目标 s 的词频，\(x\) 是每个数字出现的次数

实际上上一个解法是我们手动加减消元法解出方程组再模拟了解方程的过程

# Code language: Python
import numpy as np
class Solution:
    def originalDigits(self, s: str) -> str:
        cnt = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine']
        st = set(i for c in cnt for i in c)  # 看看出现过哪些字母
        keys = list(st)
        A = np.array([[c.count(k) for k in keys] for c in cnt])
        b = np.array([[s.count(k)] for k in keys])
        x = np.linalg.pinv(A.T).dot(b)
        return ''.join(i * round(j) for i, j in zip('0123456789', x.T.tolist()[0]))

复杂度比前一个方法高但是一个通用解法，可以随意修改数字的英文表示（当然改完要保证方程组有解否则只能得到近似解，这里没有做方程组是否只有唯一解的判断）,也可以增加 11, 12, ……, 25 都能得到结果，为什么最多只能 25 呢？因为字母只有 26 个也就是线性方程组中最多只有 26 个方程，如果未知数个数超过 26 那么就不可能只有唯一解

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』423 从英文中重建数字

题目

标签

题解

思路

方程组解法