leetcode423. Reconstruct Original Digits from English

제목 요구

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"

무질서 한 아라비아 숫자 를 포함 한 비 어 있 는 영어 문자열예 를 들 어 012 에 대응 하 는 영문 표현 은 zeroonetwo 이 고 계속 난 서 성 owoztneoer 이다.무질서 한 영문 표현 식 을 입력 하고 그 안에 포 함 된 모든 0-9 의 숫자 를 찾 아 작은 것 부터 큰 것 까지 출력 해 야 합 니 다.
아이디어 와 코드
먼저 숫자 와 영문 표 시 를 열거 합 니 다.

0 zero
1 one
2 two
3 three
4 four
5 five
6 six
7 seven
8 eight
9 nine

대충 보면 우 리 는 많은 자모 가 하나의 영문 숫자 에 만 나타 나 는 것 을 알 고 있다. 예 를 들 어 z 는 제로 에 만 나타난다.따라서 이런 자모 가 나타 나 면 이 숫자 가 반드시 나타 난 다 는 뜻 이다.따라서 한 번 여과 한 후에 한 번 만 나타 나 는 알파벳 은 다음 과 같다.

0 zero -> z
1 one
2 two -> w
3 three
4 four -> u
5 five
6 six -> x
7 seven
8 eight
9 nine

나머지 알파벳 에 한 번 만 나타 나 는 알파벳 을 걸 러 냅 니 다.

1 one 
3 three -> r
5 five -> f
7 seven -> s
8 eight -> g
9 nine

마지막 으로 원 과 나 인 을 각각 o 와 i 로 구분 하면 된다.따라서 다음 과 같은 코드 를 얻 을 수 있다.

    public String originalDigits(String s) {
        int[] letterCount = new int[26];
        for(char c : s.toCharArray()) {
            letterCount[c-'a']++;
        }
        
        int[] result = new int[10];
        
        //zero
        if((result[2] = letterCount['z'-'a']) != 0) {
            result[0] = letterCount['z' - 'a'];
            letterCount['z'-'a'] = 0;
            letterCount['e'-'a'] -= result[0];
            letterCount['r'-'a'] -= result[0];
            letterCount['o'-'a'] -= result[0];
        }
        //two
        if((result[2] = letterCount['w'-'a']) != 0) {
            letterCount['t'-'a'] -= result[2];
            letterCount['w'-'a'] = 0;
            letterCount['o'-'a'] -= result[2];
        }
        //four
        if((result[4] = letterCount['u'-'a']) != 0) {
            letterCount['f'-'a'] -= result[4];
            letterCount['o'-'a'] -= result[4];
            letterCount['u'-'a'] -= result[4];
            letterCount['r'-'a'] -= result[4];
        }
        //five
        if((result[5] = letterCount['f'-'a']) != 0) {
            letterCount['f'-'a'] -= result[5];
            letterCount['i'-'a'] -= result[5];
            letterCount['v'-'a'] -= result[5];
            letterCount['e'-'a'] -= result[5];
        }
        //six
        if((result[6] = letterCount['x'-'a']) != 0) {
            letterCount['s'-'a'] -= result[6];
            letterCount['i'-'a'] -= result[6];
            letterCount['x'-'a'] -= result[6];
        }
        //seven
        if((result[7] = letterCount['s'-'a']) != 0) {
            letterCount['s'-'a'] -= result[7];
            letterCount['e'-'a'] -= result[7] * 2;
            letterCount['v'-'a'] -= result[7];
            letterCount['n'-'a'] -= result[7];
        }
        //one
        if((result[1] = letterCount['o'-'a']) != 0) {
            letterCount['o'-'a'] -= result[1];
            letterCount['n'-'a'] -= result[1];
            letterCount['e'-'a'] -= result[1];
        }
        //eight
        if((result[8] = letterCount['g'-'a']) != 0) {
            letterCount['e'-'a'] -= result[8];
            letterCount['i'-'a'] -= result[8];
            letterCount['g'-'a'] -= result[8];
            letterCount['h'-'a'] -= result[8];
            letterCount['t'-'a'] -= result[8];
        }
        //nine
        if((result[9] = letterCount['i'-'a']) != 0) {
            letterCount['n'-'a'] -= result[9] * 2;
            letterCount['i'-'a'] -= result[9];
            letterCount['e'-'a'] -= result[9];
        }
        result[3] = letterCount['t'-'a'];
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i

위의 코드 는 너무 번 거 롭 게 썼 기 때문에 이 를 더욱 최적화 하면 다음 과 같은 코드 를 얻 을 수 있다.

    public String originalDigits2(String s) {
        int[] alphabets = new int[26];
        for (char ch : s.toCharArray()) {
            alphabets[ch - 'a'] += 1;
        }
        
        int[] digits = new int[10];
        
        digits[0] = alphabets['z' - 'a'];
        digits[2] = alphabets['w' - 'a'];
        digits[6] = alphabets['x' - 'a'];
        digits[8] = alphabets['g' - 'a'];
        digits[7] = alphabets['s' - 'a'] - digits[6];
        digits[5] = alphabets['v' - 'a'] - digits[7];
        digits[3] = alphabets['h' - 'a'] - digits[8];
        digits[4] = alphabets['f' - 'a'] - digits[5];
        digits[9] = alphabets['i' - 'a'] - digits[6] - digits[8] - digits[5];
        digits[1] = alphabets['o' - 'a'] - digits[0] - digits[2] - digits[4];
        
        StringBuilder sb = new StringBuilder();
        for (int d = 0; d < 10; d++) {
            for (int count = 0; count < digits[d]; count++) sb.append(d);
        }
        
        return sb.toString();
    }