O(n) time, O(1) space, but still Time Limit Exceeded


  • 0
    K

    Why did I get a TLE exceeded with this solution? It seems good to me.

    public class Solution {
        public String originalDigits(String s) {
            int[] characterFreqs = new int[26];
            for (char c : s.toCharArray()) {
                characterFreqs[c - 'a'] ++;
            }
            
            int[] numberFreqs = new int[10];
            for (char indicator : indicators) {
                int index = indicator - 'a';
                while (characterFreqs[index] > 0) {
                    numberFreqs[numbers[index]] ++;
                    for (char c : words[index]) {
                        characterFreqs[c - 'a'] --;
                    }
                }
            }
            
            String result = "";
            for (int i = 0; i < numberFreqs.length; i ++) {
                for (int j = 0; j < numberFreqs[i]; j ++) {
                    result += String.format("%d", i);
                }
            }
            
            return result;
        }
        
        private static final char[] indicators = {'z','w','u','x','g','o','r','f','s','i'};
            
        private static final char[][] words = new char[26][];
        static {
            words['z' - 'a'] = new char[] {'z','e','r','o'};
            words['w' - 'a'] = new char[] {'t','w','o'};
            words['u' - 'a'] = new char[] {'f','o','u','r'};
            words['x' - 'a'] = new char[] {'s','i','x'};
            words['g' - 'a'] = new char[] {'e','i','g','h','t'};
            words['o' - 'a'] = new char[] {'o','n','e'};
            words['r' - 'a'] = new char[] {'t','h','r','e','e'};
            words['f' - 'a'] = new char[] {'f','i','v','e'};
            words['s' - 'a'] = new char[] {'s','e','v','e','n'};
            words['i' - 'a'] = new char[] {'n','i','n','e'};
        }
        
        private static final int[] numbers = new int[26];
        static {
            numbers['z' - 'a'] = 0;
            numbers['w' - 'a'] = 2;
            numbers['u' - 'a'] = 4;
            numbers['x' - 'a'] = 6;
            numbers['g' - 'a'] = 8;
            numbers['o' - 'a'] = 1;
            numbers['r' - 'a'] = 3;
            numbers['f' - 'a'] = 5;
            numbers['s' - 'a'] = 7;
            numbers['i' - 'a'] = 9;
        }
    }
    
    

Log in to reply
 

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