C++ O(n) solution


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

  • 0
    K

    @orientallee My logic is exactly similar but your code is very small and clean. Kudos :)


  • 0
    M

    @orientallee Very nice logic and implementation. I had the same idea for even numbers, but I didn't get it for the odd ones. Thanks for sharing.


  • 0
    M

    I code same like your,however I'am wrong answer.
    *WA case:input "zeor" ouput “045” Why? I can't understand.

     char * originalDigits(char* s)
    {
        int *ch=(int *)malloc(128*sizeof(int));
        int i,len;char *p=s;
        int zero,one,two,three,four,five,six,seven,eight,nine;
        zero=one=two=three=four=five=six=seven=eight=nine=0;
        while(*p)
            ch[*p++]++;
        zero=ch['z'];
        one=ch['o']-ch['z']-ch['w']-ch['u'];
        two=ch['w'];
        three=ch['h']-ch['g'];
        four=ch['u'];
        five=ch['f']-ch['u'];
        six=ch['x'];
        seven=ch['s']-ch['x'];
        eight=ch['g'];
        nine=ch['i']-eight-six-five;
        len=zero+one+two+three+four+five+six+seven+eight+nine;
        char *res=(char *)malloc(sizeof(char)*(len+1));
        p=res;
        p=memset(p,'0',zero);p+=zero;
        p=memset(p,'1',one);p+=one;
        p=memset(p,'2',two);p+=two;
        p=memset(p,'3',three);p+=three;
        p=memset(p,'4',four);p+=four;
        p=memset(p,'5',five);p+=five;
        p=memset(p,'6',six);p+=six;
        p=memset(p,'7',seven);p+=seven;
        p=memset(p,'8',eight);p+=eight;
        p=memset(p,'9',nine);p+=nine;
        *p='\0';
        free(ch);
        return res;
    }

  • 0
    M

    @mingxiaoshan

    It happened also to me for some problems to get different results when i run my code versus when i submit it. I believe there are different compilers. So I run your code for "zeor" and it prints "0" and at submission it prints, indeed "045".
    I added this line: for (int i = 0; i < 128; ++i) ch[i] = 0;
    And your solution is accepted


  • 0
    M

    @mhush Thank you very much! My code habit is not good :)


Log in to reply
 

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