Share my simple and easy O(N) solution


  • 17
    public class Solution {
        public String originalDigits(String s) {
            if(s==null || s.length()==0) return "";
            int[] count = new int[128];
            for(int i=0;i<s.length();i++)  count[s.charAt(i)]++;
            int[] num = new int[10];
            num[0] = count['z'];
            num[2] = count['w'];
            num[4] = count['u'];
            num[6] = count['x'];
            num[8] = count['g'];
            num[1] = count['o']-count['z']-count['w']-count['u'];
            num[3] = count['h']-count['g'];
            num[5] = count['v']-count['s']+count['x'];
            num[7] = count['s']-count['x'];
            num[9] = count['i']-count['x']-count['g']-count['v']+count['s']-count['x'];
            String ret = new String();
            for(int i=0;i<10;i++)
                for(int j=num[i];j>0;j--) ret += String.valueOf(i);
            return ret;
        }
    }
    

  • 5
    K

    I think following is better

    // even numbers all have unique letter 
            countNum[0] = countChar['z'];
            countNum[2] = countChar['w'];
            countNum[4] = countChar['u'];
            countNum[6] = countChar['x'];
            countNum[8] = countChar['g'] ;
            
            countNum[7] = countChar['s'] - countNum[6];
            countNum[5] = countChar['v'] - countNum[7];
            countNum[3] = countChar['h'] - countNum[8];
            countNum[1] = countChar['o'] - countNum[2] - countNum[4] - countNum[0];
            countNum[9] = countChar['i'] - countNum[6] - countNum[5] - countNum[8] ;
    

  • 0
    R

    @krisdu
    Agree you are better, I will probably ask the eng to rewrote the origin solution since it is not easily readable.


  • 0
    Z

    Thanks for the solution! 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;
        }
    };
    

Log in to reply
 

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