423. 從英文中重建數字 : 腦筋急轉彎模拟題

題目描述

這是 LeetCode 上的 ​​423. 從英文中重建數字​​ ，難度為 中等。

Tag : 「模拟」、「腦筋急轉彎」

給你一個字元串 ​

​s​

​​ ，其中包含字母順序打亂的用英文單詞表示的若幹數字​

​（0-9）​

​。按 升序 傳回原始的數字。

示例 1：

輸入：s = "owoztneoer"

輸出："012"      

示例 2：

輸入：s = "fviefuro"

輸出："45"      

提示：

• ​

  ​s[i]​

  ​​ 為​

  ​["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"]​

  ​ 這些字元之一
• ​

  ​s​

  ​ 保證是一個符合題目要求的字元串

模拟

題目要求我們将打亂的英文單詞重建為數字。

我們可以先對 ​

​s​

​ 進行詞頻統計，然後根據「英文單詞中的字元唯一性」确定建構的順序，最後再對答案進行排序即可。

具體的，​

​zero​

​​ 中的 ​

​z​

​​ 在其餘所有單詞中都沒出現過，我們可以先統計 ​

​zero​

​​ 的出現次數，并建構 ；然後觀察剩餘數字，其中 ​​

​eight​

​​ 中的 ​

​g​

​​ 具有唯一性，建構 ；再發現 ​​

​six​

​​ 中的 ​

​x​

​​ 具有唯一性，建構 ；發現 ​​

​three​

​​ 中的 ​

​h​

​​ 具有唯一性（利用在此之前 ​

​eight​

​​ 已經被删除幹淨，詞頻中僅存在 ​

​three​

​​ 對應的 ​

​h​

​​)，建構 ...

最終可以确定一個可行的建構序列為 ​

​0, 8, 6, 3, 2, 7, 5, 9, 4, 1​

​。

代碼：

class Solution {
    static String[] ss = new String[]{"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    static int[] priority = new int[]{0, 8, 6, 3, 2, 7, 5, 9, 4, 1};
    public String originalDigits(String s) {
        int n = s.length();
        int[] cnts = new int[26];
        for (int i = 0; i < n; i++) cnts[s.charAt(i) - 'a']++;
        StringBuilder sb = new StringBuilder();
        for (int i : priority) {
            int k = Integer.MAX_VALUE;
            for (char c : ss[i].toCharArray()) k = Math.min(k, cnts[c - 'a']);
            for (char c : ss[i].toCharArray()) cnts[c - 'a'] -= k;
            while (k-- > 0) sb.append(i);
        }
        char[] cs = sb.toString().toCharArray();
        Arrays.sort(cs);
        return String.valueOf(cs);
    }
}      

• 時間複雜度：令為最終答案的長度，為所有英文單詞的字元總長度。建構答案的複雜度為；對建構答案進行排序複雜度為。整體複雜度為
• 空間複雜度：

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.423​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。