Simple O(N) solution based on prior frequency analysis


  • 0
    I
    public class Solution {
        //freq 1: g, u, w, x, z
        //eight
        //four
        //two
        //six
        //zero
        
        //freq 2: f, h, s
        //five (four)
        //three (eight)
        //seven (six)
    
        //freq 4: o, n
        //one (zero, two, four)
        //nine (one, seven), but note that 'n' appears twice in "nine"
        
        public String originalDigits(String s) {
            final char[] str = s.toCharArray();
    
            final int[] paper = new int[10];
            
            for(int i=0; i<str.length; i++) {
                switch (str[i]) {
                    case 'g':
                        paper[8]++;
                        break;
                    case 'u':
                        paper[4]++;
                        break;
                    case 'w':
                        paper[2]++;
                        break;
                    case 'x':
                        paper[6]++;
                        break;
                    case 'z':
                        paper[0]++;
                        break;
                    case 'f':
                        paper[5]++;
                        break;
                    case 'h':
                        paper[3]++;
                        break;
                    case 's':
                        paper[7]++;
                        break;
                    case 'o':
                        paper[1]++;
                        break;
                    case 'n':
                        paper[9]++;
                        break;
                    default:
                        break;
                }
            }
            
            paper[5] -= paper[4];
            paper[3] -= paper[8];
            paper[7] -= paper[6];
            
            paper[1] -= paper[0] + paper[2] + paper[4];
            
            paper[9] = (paper[9] - paper[1] - paper[7]) >> 1;
    
            int sum = 0;
            for(int i=0; i<10; i++) {
                sum += paper[i];
            }
            
            final char[] ans = new char[sum];
            
            for(int index = 0, i=0; i<10; i++) {
                Arrays.fill(ans, index, (index += paper[i]), (char)(i + '0'));
            }
            
            return new String(ans);
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.