Straightforward C++ Accepted Solution


  • 9
    class Solution {
    public:
        string originalDigits(string s) {
            vector<string> words = {"zero", "two", "four", "six", "eight", "one", "three", "five", "seven", "nine"};
            vector<int> nums = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
            vector<int> distinct_char = {'z', 'w', 'u', 'x', 'g', 'o', 'r', 'f', 'v', 'i'};
            vector<int> counts(26, 0);
            string result;
            for(auto ch : s){ counts[ch-'a']++;}
            for(int i = 0; i < 10; i++){
                int count = counts[distinct_char[i]-'a'];
                for(int j = 0; j < words[i].size(); j++)
                    counts[words[i][j]-'a'] -= count;
                while(count--)
                    result += to_string(nums[i]);
            }
            sort(result.begin(), result.end());
            return result;
        }
    };
    

  • 1
    B

    This is great and elegant! Thanks for sharing the solution.


  • 0
    W

    @Undo Very concise code, nice solution! But I think we can use bucket sort to make it faster : )

    string originalDigits(string s) {
            vector<pair<int, char> > table = {
                {2, 'w'}, {4, 'u'}, {6, 'x'}, {8, 'g'}, {0, 'z'}, {3, 'r'}, {7, 's'}, {5, 'v'}, {1, 'o'}, {9, 'i'}
            };
            vector<string> translate = {
                "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"
            };
            vector<int> mp(256, 0), record(10, 0);
            for(auto c: s) mp[c]++;
            for(auto& p: table) {
                int count = mp[p.second];
                record[p.first] = count;
                for(auto c: translate[p.first]) mp[c] -= count;
            }
            ostringstream os;
            for(int i = 0; i < 10; i++) {
                int count = record[i];
                while(count--) os << i;
            }
            return os.str();
        }
    

  • 1
    Z

    Here is my C++ code.

    class Solution {
    public:
        string originalDigits(string s) {
            vector<int> mp(26, 0), nums(10, 0);
            for (char c:s) mp[c-'a']++;
            nums[0] = mp['z'-'a'];
            nums[2] = mp['w'-'a'];
            nums[4] = mp['u'-'a'];
            nums[1] = mp['o'-'a']-nums[0]-nums[2]-nums[4];
            nums[3] = mp['r'-'a']-nums[0]-nums[4];
            nums[6] = mp['x'-'a'];
            nums[7] = mp['s'-'a']-nums[6];
            nums[8] = mp['g'-'a'];
            nums[5] = mp['v'-'a']-nums[7];
            nums[9] = mp['i'-'a']-nums[5]-nums[6]-nums[8];
            string ans;
            for (int i = 0; i < 10; i++) {
                ans += string(nums[i],'0'+i);
            }
            return ans;
        }
    };
    

  • 0
    V

    @Undo I think if we keep the vector<string> words and vector<int> distinct_char in sorted order, we can avoid sort at the end. Any thoughts?


  • 1
    T

    great solution! re-write your method using Java:

    class Solution {
        public String originalDigits(String s) {
            String[] words = {"zero", "two", "four", "six", "eight", "one", "three", "five", "seven", "nine"};
            int[] nums = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
            int[] distinct_char = {'z', 'w', 'u', 'x', 'g', 'o', 'r', 'f', 'v', 'i'};
            
            
            int[] counts = new int[26];
            for(int i=0;i<s.length();i++){
                counts[s.charAt(i)-'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<words.length;i++){
                int count = counts[distinct_char[i]-'a'];
                for(int j=0;j<words[i].length();j++){
                    counts[words[i].charAt(j)-'a']-=count;
                }
                while(count--!=0){
                    sb.append(nums[i]);
                }
            }
            
            char[] nums_str = sb.toString().toCharArray();
            Arrays.sort(nums_str);
            return new String(nums_str);
        }
    }
    
    

Log in to reply
 

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