ReconstructOriginalDigitsFromEnglish [source code]
public class ReconstructOriginalDigitsFromEnglish {
static
/******************************************************************************/
class Solution {
public String originalDigits(String s) {
String[] digits = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
char[] chs = s.toCharArray();
if (s.length() < 3)
return "";
int[] counts = new int[26]; //counts of chars in s
int[] order = {0,2,4,6,8, 3,5,7, 1,9}; //array of indices of digits to visit, ordered based on rarity of chars
int[] res = new int[10]; //array to store and sort the result
for (char c : chs) //count chars in s
counts[c - 'a']++;
for (int i = 0; i < 10; i++) {
int index = order[i];
char[] chd = digits[index].toCharArray();
int min = 50000;
for (char c : chd) {
int count = counts[c - 'a'];
if ((i == 3 && c == 'e') ||
(i == 7 && c == 'e') ||
(i == 9 && c == 'n'))
count /= 2;
if (count < min)
min = count;
} //count is now the maximum number of copies of word_for_index we can extract from s
if (min <= 0) //abort if no copies available
continue;
for (char c : chd) //subtract char counts to reflect `min` copies extracted
counts[c - 'a'] -= min;
res[index] += min; //output to res
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 10; i++) {
for (int j = 0; j < res[i]; j++) {
sb.append(i);
}
}
return sb.toString();
}
}
/******************************************************************************/
public static void main(String[] args) {
ReconstructOriginalDigitsFromEnglish.Solution tester = new ReconstructOriginalDigitsFromEnglish.Solution();
String[] inputs = {
"owoztneoer", "012",
"fviefuro", "45",
"zeroonetwothreefourfivesixseveneightnine", "0123456789",
};
for (int i = 0; i < inputs.length / 2; i++) {
String s = inputs[2 * i];
String ans = inputs[1 + 2 * i];
System.out.println(Printer.separator());
String output = tester.originalDigits(s);
System.out.println(
Printer.wrapColor(s, "magenta") +
" -> " + output +
Printer.wrapColor(", expected: " + ans, ans.equals(output) ? "green" : "red")
);
}
}
}
这个题目刚看到的时候也是一头包, 不过最后一边做一边改居然还做出来了, 速度是13ms (88%), 也不错;
总体的思路就是把这个string的所有的char看成是所有这些数字的word的char所堆积起来的一个heap一样的东西; 能够想到这个抽象模型, 那么下面要做的事情其实就简单了, 只要挨个每个数字的word, 从这个heap里面抽出尽可能多的copy数量就可以了; 但是最后写代码的时候, 有些地方需要注意:
- three, seven, nine这三个数字, 都有一个char是重复出现的, 这个就要特别处理; 我这里的程序里面的count其实是记录的最大可以抽出掉的copy数量, 计算方式是这个word里面, 哪个char的剩余数量最少, 那么count就是这个; 但是轮到这三个数字当中的重复char的时候, 就需要对半一下;
- 刚开始我的想法还是给每一个word, 比如three, 来一个类似于{t=1, h= 1, r=1, e=2}这样的字典结构, 这样所有的word都可以统一处理; 但是这里还是犯了一个以前警告过的错误: obsession with generality. 这就是一个很具体的问题, 我们就是只有10个word, 你能够照顾好这十个的个性就可以了; 不要总想着"假如我们有一百个标准word怎么办"这样根本不存在的情形, 不要给自己加戏!
- 一个很重要的问题, 当时没有想到, 就是这个抽出的顺序, 总共九个数字, 默认顺序真的可以吗? 有点像当时CHH上面有一道题目的时候, 当时也是很单纯的, 直接就按照默认的顺序来做, 最后就没有完成最正确的搜索; 这里这个类似value ordering的问题, 需要思考;
- 当然, 一个最简单的思路就是用解决当时CHH那一道题目的思路, 直接backtracking就可以了; 这个属于不确定搜索, 也就是穷搜; 当然我感觉是可以的, 最后要确定的一个条件就是当所有的数字都被抽完, 抽到无法继续抽的时候, heap也清空了;
- 但是这样一个问题, 真的需要用到不确定搜索吗? 事实上, 这个问题直接确定搜索就可以了; 脑子里面visual一下, 26个汉诺塔一样的东西, 不同的高度, 一次从底下抽掉一定的层数; 你觉得什么样的word应该先抽? 没错, 就是constituent在"zeroonetwothreefourfivesixseveneightnine"当中出现次数最少的开始抽起. 比如z,x,w,u,g分别只出现一次, 根据这些决定第一批次抽出来的应该是zero, two, four, six, eight; 依此继续;
- 这个ordering我现在其实还没有十足的把握就说是一定正确; 不过直观上感觉应该是对的; 把最稀缺的几个字母先给分配出去, 然后剩下的大众脸随便分配就行了;
- 题目还有一个要求, 就是最后输出要排序; 在没有意识到ordering, 也就是刚开始无脑用默认ordering做的时候, 这个要求没有什么问题, 直接就是按照顺序output就行了; 但是这里我们因为需要按照一个比较混乱的顺序去处理, 最后就不可能指望一个自然的排序了; 有两个地方要思考一下怎么实现:
- 怎么实现这个处理顺序, 也就是这个三个批次; 我刚开始的想法就是把这个string array直接按照批次的优先级来排序, 然后后面有一个问题, 这个word你怎么知道是什么int? 唯一想到的办法就是自己重新写一个反向查询, 能够把zero翻译成0, 不过这样就感觉有点麻烦, 我还是想利用默认的排序的时候index和word的自然对应; 顺着这个思路, 想到的办法是一个425project的时候用到过的类似的思想: index array. 我们最终想要实现的一个ordering是针对word的, 但是我这里希望维持一个index和word能一一对应的默认排序, 那么我们只要把这个本来应该应用到word上面的ordering, 应用到index上面就行了; 所以专门做一个array用来装index, 这个array里面可以体现这个ordering; 这个思路刚开始碰到的时候可能确实感觉有点奇怪, 不过其实就是加一层中转的映射关系;
- 上面解决的是一个类似input ordering的问题, 那么output ordering怎么解决; 刚开始没有想到, 还想着专门最后再来一个排序, 这个就很麻烦; 其实这里用一个类似bucket sort的思路来做就行了, 所有的数字, 反正总共就十个, 全都统计count, 然后最后按照顺序倒出来就行了;
总体来说这个不是一个非常复杂的题目, 不过还是考察了很多基本功的;
这个是discussion最优解, 基本的思路其实跟我的算法是差不多的:
@markieff said in one pass O(n) JAVA Solution, Simple and Clear:
The idea is:
for zero, it's the only word has letter 'z',
for two, it's the only word has letter 'w',
......
so we only need to count the unique letter of each word, Coz the input is always valid.Code:
public String originalDigits(String s) {
int[] count = new int[10];
for (int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if (c == 'z') count[0]++;
if (c == 'w') count[2]++;
if (c == 'x') count[6]++;
if (c == 's') count[7]++; //7-6
if (c == 'g') count[8]++;
if (c == 'u') count[4]++;
if (c == 'f') count[5]++; //5-4
if (c == 'h') count[3]++; //3-8
if (c == 'i') count[9]++; //9-8-5-6
if (c == 'o') count[1]++; //1-0-2-4
}
count[7] -= count[6]; //share s
count[5] -= count[4]; //share f
count[3] -= count[8]; //share e
count[9] = count[9] - count[8] - count[5] - count[6]; //share i
count[1] = count[1] - count[0] - count[2] - count[4]; //share o
StringBuilder sb = new StringBuilder();
for (int i = 0; i <= 9; i++){
for (int j = 0; j < count[i]; j++){
sb.append(i);
}
}
return sb.toString();
}
但是他对于这个rare字母的概念使用的更加极端, 他直接先count出现次数最少的字母, 然后count出现次数第二少的, 依次类推; 他看到的一个intuition就是, 我们这里可以这样理解, 我的思路其实是类似一个减法思维, 我是假设先有这个heap, 然后从这里面拿出去一个一个的word; 他这里的思路其实更接近与一个加法思维: 在他的思路里面, 一个word给这个heap就贡献了这么多的字母; 比如s这个字母, 只有six和seven包含, 只有这两个单词会贡献; 所以如果我们知道了s的个数, 我们就知道了six和seven的总数, 但是我们怎么知道分配呢? 因为six里面还有一个x, 这个x只有six可以贡献, 所以通过数x我们就可以知道six的个数, 然后seven的个数就知道了; 当然实际上的这个递推关系比这个要复杂依稀而, 比如4可以用u计算出来, 然后用4计算出来了5, 用5又要去帮助计算9; 我感觉我的做法其实是一个比较直白的计算的方法, 而他这里的这个方法更像是一个智力上的推理; 而且他这个代码虽然看起来比我的代码简单很多, 但是实际上背后的逻辑并不我的简单; 我的代码虽然很长, 但是背后的逻辑其实比他这个简单好理解很多;
这个是另外一个类似的版本:
static String[] digits = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
static char[] ids = {'z', 'o', 'w', 'h', 'u', 'f', 'x', 's', 'g', 'i'};
static int[] order = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
public String originalDigits(String s) {
int[] dCount = new int[10], lCount = new int[26];
for (char c : s.toCharArray()) lCount[c - 'a']++;
for (int d : order) {
dCount[d] = lCount[ids[d] - 'a'];
for (char c : digits[d].toCharArray()) lCount[c - 'a'] -= dCount[d];
}
StringBuilder ans = new StringBuilder();
for (int i = 0; i < 10; ++i) {
for (int j = 0; j < dCount[i]; ++j) ans.append(i);
}
return ans.toString();
}
这个看起来其实很像我的版本, 但是实际上还是一个跟这里的discussion1更加接近的版本, 最后想要做到的还是类似于用一个char去代表一个word的工作; 只不过他这里的最后的顺序安排的比较合理, 直接按照顺序减就可以了; 他这里的虽然最后的代码是一个减法思维, 但是背后透露的其实还是跟上面一样的加法思维;
有人认为按照奇偶性来递推更加好:
// even numbers all have unique letter
countNum[0] = countChar['z'];
countNum[2] = countChar['w'];
countNum[4] = countChar['u'];
countNum[6] = countChar['x'];
countNum[8] = countChar['g'] ;
countNum[7] = countChar['s'] - countNum[6];
countNum[5] = countChar['v'] - countNum[7];
countNum[3] = countChar['h'] - countNum[8];
countNum[1] = countChar['o'] - countNum[2] - countNum[4] - countNum[0];
countNum[9] = countChar['i'] - countNum[6] - countNum[5] - countNum[8] ;
其他的基本没有什么更好的解法了, 大概都是这么一回事了;
Problem Description
Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.
Note:
- Input contains only lowercase English letters.
- Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as "abc" or "zerone" are not permitted.
- Input length is less than 50,000.
Example 1:
Input: "owoztneoer"
Output: "012"
Example 2:
Input: "fviefuro"
Output: "45"
Difficulty:Medium
Total Accepted:11.6K
Total Submissions:26.2K
Contributor: LeetCode
Related Topics
math