423.从英文中重建数字

链接：423.从英文中重建数字
难度：Medium
标签：哈希表、数学、字符串
简介：给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字。

题解 1 - typescript

• 编辑时间：2021-11-24
• 执行用时：124ms
• 内存消耗：41.3MB
• 编程语言：typescript
• 解法介绍：对于数字一次排序删减。

const dict: Record<number, string[]> = {
  1: 'one'.split(''),
  2: 'two'.split(''), // w
  3: 'three'.split(''), //t
  4: 'four'.split(''), // u
  5: 'five'.split(''), // f
  6: 'six'.split(''), // x
  7: 'seven'.split(''), // v
  8: 'eight'.split(''), // g
  9: 'nine'.split(''), // i
  0: 'zero'.split(''), // z
};
const checkList = [
  { num: 2, key: 'w' },
  { num: 6, key: 'x' },
  { num: 0, key: 'z' },
  { num: 8, key: 'g' },
  { num: 3, key: 't' },
  { num: 4, key: 'u' },
  { num: 5, key: 'f' },
  { num: 7, key: 'v' },
  { num: 9, key: 'i' },
  { num: 1, key: 'o' },
];
function originalDigits(s: string): string {
  const map: Record<string, number> = {};
  for (const c of s) map[c] = (map[c] ?? 0) + 1;
  const list: number[] = new Array(10).fill(0);
  for (const { num, key } of checkList) {
    if (!map[key]) continue;
    const cnt = map[key];
    list[num] += cnt;
    for (const ch of dict[num]) map[ch] -= cnt;
  }
  return list.reduce((ans, cnt, num) => ans + num.toString().repeat(cnt), '');
}

题解 2 - c

• 编辑时间：2021-11-24
• 执行用时：276ms
• 内存消耗：6.3MB
• 编程语言：c
• 解法介绍：对于数字一次排序删减。

struct {
    int num;
    char key;
} checkList[10] = {
    {2, 'w'}, {6, 'x'}, {0, 'z'}, {8, 'g'}, {3, 't'},
    {4, 'u'}, {5, 'f'}, {7, 'v'}, {9, 'i'}, {1, 'o'}
};
char dict[10][6] = {
    {"zero"}, {"one"}, {"two"},{"three"}, {"four"},
    {"five"}, {"six"}, {"seven"}, {"eight"}, {"nine"}
};
char * originalDigits(char * s){
    int map[26] = {0}, list[10] = {0}, sum = 0;
    for (int i = 0; i < strlen(s); i++) map[s[i] - 'a']++;
    for (int i = 0; i < 10; i++) {
        char key = checkList[i].key;
        int num = checkList[i].num;
        if (!map[key - 'a']) continue;
        int cnt = map[key - 'a'];
        list[num] += cnt;
        sum += cnt;
        for (int i = 0; i < strlen(dict[num]); i++) {
            char ch = dict[num][i];
            map[ch - 'a'] -=cnt;
        }
    }
    int idx = 0;
    char *ans = (char *)malloc(sizeof(char) * (sum + 1));
    ans[sum] = '\0';
    for (int num = 0; num < 10; num++) {
        int cnt = list[num];
        if (!cnt) continue;
        memset(ans + idx, num + '0', sizeof(char) * cnt);
        idx += cnt;
        // printf("sum = %d, num = %d, cnt = %d, ans = %s\n", sum, num, cnt, ans);
    }
    // printf("ans = %s\n", ans);
    return ans;
}