Clean java o(n) solution with explanation


  • 0
    F

    Clean java solution

    1. zero, two, six eight, have distinct character z, w, x, g
    2. other characters are only shared by word with known count and only another word with unknown count, like six and seven share 's', seven and five share 'v'
    class Solution {
        public String originalDigits(String s) {
            int[] cc = new int[256];
            int[] dc = new int[10];
            for (char c: s.toCharArray()) {
                ++cc[c];
            }
            String[] order = {"zero", "six", "seven", "five", "four", "two", "eight", "three", "one", "nine"};
            char[] flag = {'z', 'x', 's', 'v', 'f', 'w', 'g', 'r', 'o', 'i'};
            int[] digits = {0, 6, 7, 5, 4, 2, 8, 3, 1, 9};
            for (int i = 0; i< 10; ++i) {
                int n = cc[flag[i]];
                if (n > 0) {
                    dc[digits[i]] = n;
                    for (char c: order[i].toCharArray()) cc[c] -=n;
                }
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i <= 9; ++i) {
                for (int j = 0; j < dc[i]; ++j)
                    sb.append(i);
            }
            return sb.toString();
            
        }
    }
    

Log in to reply
 

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