Solution by <644367822>


  • 0
    6

    Approach #1 Simple Solution with Hash Table[Accept]

    Algorithm

    First we can find the characters 'z' of "zero" is unique and 'w' of "two" is unique as well the 'u' of "four" and 'x' of "six".

    So we can easily count the number of '0' , '2' , '4' ,'6' .

    According to this thought we will solve the problem with follow steps .

    1 Calculate the number of characters

      int hash[26];
      memset( hash , 0 ,sizeof( hash ) ) ;
      for( int i=0 ; i < s.size() ; i ++) {
          hash[ s[i] - 'a' ] ++;
      }
    

    2 New a array to save the count of number

      int nums[10];
      memset( nums , 0 , sizeof( nums ) );
    

    3 Now we count the number of '0', '2' , '4' , '6' . But the point is when we count the number
    ,we should minus the other characters .

    For example ,when we calculate the character 'z' of "zero", meanwhile ,
    we should minus the number of other character 'e' , 'r' , 'o' .

    if( hash['z'-'a'] !=  0) {
       nums[0] = hash['z'-'a'];
       hash['e'-'a'] -= nums[0];
       hash['r'-'a'] -= nums[0];
       hash['o'-'a'] -= nums[0];
    }
    

    4 After we count the number of '0' , '2' , '4' , '6' . the 'g' of "eight" is unique .

    5 After we count the number of '8' . the 'h' of "three" is unique.

    6 Similar of above .

    c++

    class Solution {
    public:
        string originalDigits(string s) {
            int hash[26] ;
            memset( hash , 0 , sizeof( hash ) ) ;
            for( int i = 0 ; i < s.size() ; i ++ ) {
                hash[ s[i] - 'a' ] ++ ;
            }
            int nums[10];
            memset( nums , 0 , sizeof( nums ) ) ;
            //0
            if( hash[ 'z' - 'a' ] ) {
                nums[0] = hash[ 'z' - 'a' ] ;
                hash[ 'e' - 'a' ] -= nums[0] ;
                hash[ 'r' - 'a' ] -= nums[0] ;
                hash[ 'o' - 'a' ] -= nums[0] ;
            }
            //2
            if( hash[ 'w' - 'a' ] ) {
                nums[2] = hash[ 'w' - 'a' ] ;
                hash[ 't' - 'a' ] -= nums[2] ;
                hash[ 'o' - 'a' ] -= nums[2] ;
            }
            //4
            if( hash[ 'u' - 'a' ] ) {
                nums[4] = hash[ 'u' - 'a' ] ;
                hash[ 'f' - 'a' ] -= nums[4] ;
                hash[ 'o' - 'a' ] -= nums[4] ;
                hash[ 'r' - 'a' ] -= nums[4] ;
            }
            //6
            if( hash[ 'x' - 'a' ] ) {
                nums[6] = hash[ 'x' - 'a' ] ;
                hash[ 's' - 'a' ] -= nums[6] ;
                hash[ 'i' - 'a' ] -= nums[6] ;
            }
            //8
            if( hash[ 'g' - 'a' ] ) {
                nums[8]=hash[ 'g' - 'a' ] ;
                hash[ 'e' - 'a' ] -= nums[8] ;
                hash[ 'i' - 'a' ] -= nums[8] ;
                hash[ 'h' - 'a' ] -= nums[8] ;
                hash[ 't' - 'a' ] -= nums[8] ;
            }
            //3
            if( hash[ 'h' - 'a' ] ) {
                nums[3]=hash[ 'h' - 'a' ] ;
                hash[ 't' - 'a' ] -= nums[3] ;
                hash[ 'r' - 'a' ] -= nums[3] ;
                hash[ 'e' - 'a' ] -= nums[3] ;
            }
            //5
            if( hash[ 'f' - 'a' ] ) {
                nums[5] = hash[ 'f' - 'a' ] ;
                hash[ 'i' - 'a' ] -= nums[5] ;
                hash[ 'v' - 'a' ] -= nums[5] ;
                hash[ 'e' - 'a' ] -= nums[5] ;
            }
            //1
            if( hash[ 'o' - 'a' ] ) {
                nums[1] = hash[ 'o' - 'a' ] ;
            }
            //7
            if( hash[ 's' - 'a' ] ) {
                nums[7] = hash[ 's' - 'a' ] ;
            }
            //9
            if( hash[ 'i' - 'a' ] ) {
                nums[9] = hash[ 'i' - 'a' ] ;
            }
            string ans;
            for( int i = 0 ; i < 10 ; i ++ ) {
                while( nums[i] > 0 ) {
                    ans.push_back( i + '0' ) ;
                    nums[i] -- ;
                }
            }
            return ans;
        }
    };
    

    Complexity Analysis

    • Time complexity : $O(n)$. We take $O(n)$ to Calculate the number of characters ,then take $O(1)$ to carry out the operation

    • Space complexity : $O(1)$ .


Log in to reply
 

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