one pass O(n) JAVA Solution, Simple and Clear


  • 105

    The idea is:

    for zero, it's the only word has letter 'z',
    for two, it's the only word has letter 'w',
    ......
    so we only need to count the unique letter of each word, Coz the input is always valid.

    Code:

    public String originalDigits(String s) {
        int[] count = new int[10];
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (c == 'z') count[0]++;
            if (c == 'w') count[2]++;
            if (c == 'x') count[6]++;
            if (c == 's') count[7]++; //7-6
            if (c == 'g') count[8]++;
            if (c == 'u') count[4]++; 
            if (c == 'f') count[5]++; //5-4
            if (c == 'h') count[3]++; //3-8
            if (c == 'i') count[9]++; //9-8-5-6
            if (c == 'o') count[1]++; //1-0-2-4
        }
        count[7] -= count[6];
        count[5] -= count[4];
        count[3] -= count[8];
        count[9] = count[9] - count[8] - count[5] - count[6];
        count[1] = count[1] - count[0] - count[2] - count[4];
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <= 9; i++){
            for (int j = 0; j < count[i]; j++){
                sb.append(i);
            }
        }
        return sb.toString();
    }

  • 3
    A

    Wow..this is what we call, out-of-the-box


  • 0
    This post is deleted!

  • 5
    I

    Similar idea.

    static String[] digits = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    static char[] ids = {'z', 'o', 'w', 'h', 'u', 'f', 'x', 's', 'g', 'i'};
    static int[] order = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
    
    public String originalDigits(String s) {
        int[] dCount = new int[10], lCount = new int[26];
        for (char c : s.toCharArray()) lCount[c - 'a']++;
        for (int d : order) {
            dCount[d] = lCount[ids[d] - 'a'];
            for (char c : digits[d].toCharArray()) lCount[c - 'a'] -= dCount[d];
        }
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < 10; ++i) {
            for (int j = 0; j < dCount[i]; ++j) ans.append(i);
        }
        return ans.toString();
    }
    

  • 13
    J

    accept my knee


  • 0

    @markieff too bad I can only give this one up vote, this is spot on.


  • 0

    @jdrogin Thanks man, one is enough : )


  • 0
    A

    @markieff nice solution! how did you come up with the order? does it matter? also how did you decide on the character to match per digit? for instance why not look for 'v' for 5?


  • 1

    @apt275

    @markieff nice solution! how did you come up with the order? does it matter? also how did you decide on the character to match per digit? for instance why not look for 'v' for 5?

    The order of settings count[i] is extremely critical here. It is determined by "uniqueness level" (I made up the name) of a word, which is

    • UL(w) = min { ShareCount(c): all char c in word w},

    where ShareCount(c) means how many words in "zero"~"nine" contain this char.

    Then the count of any word with lowest UL(w) = 1 can be determined first (e.g., UL("zero") = 1 for 'z'), then count of any word with next lowest UL(w) = 2 can be determined right after (e.g. UL("five") = 2 for "f" after "four" which has UL("four") = 1 for 'u').

    Sorry that this notation seems very "geeky" but it is really how it works. You could generalize this into any set of words, and the "uniqueness level" roughly defines a topological sort order (although there might be cases we could have multiple answers depending on the uniqueness of the generic word set)


  • 1

    @apt275 The direct way to find the order is just write down these ten words: zero, one, two, ..., and find those have unique letters, it's pretty easy to find Cuz there are only ten words here.
    Of course you can use 'v' for 5, then it will be count[5] -= count[7]. The result is the same, so the order doesn't matter, as long as you calculate 5 after 7.


  • -1

    First count the numbers that has special character.
    Then compute numbers has common characters with those numbers.

    public String originalDigits(String s) {
      char[] sc = s.toCharArray();
      int[] count = new int[10];
      for(char c: sc){
        switch(c){
          case 'z': count[0]++; break; // zero
          case 'w': count[2]++; break; // two
          case 'u': count[4]++; break; // four
          case 'x': count[6]++; break; // six
          case 'g': count[8]++; break; // eight
          case 's': count[7]++; break; // = (six, seven) 
          case 'f': count[5]++; break; // = (four, five)
          case 'o': count[1]++; break; // = (zero, one, two, four)
          case 't': count[3]++; break; // = (two, three, eight)
          case 'i': count[9]++; break; // = (five, six, eight, nine) 
        }
      } 
      count[7] = count[7] - count[6];
      count[5] = count[5] - count[4];
      count[1] = count[1] - count[0] - count[2] - count[4];
      count[3] = count[3] - count[2] - count[8];
      count[9] = count[9] - count[5] - count[6] - count[8];
      
      StringBuilder sb = new StringBuilder();
      for(int i = 0; i < 10; i++){
        for(int j = 0; j < count[i]; j++){
          sb.append(i);
        }
      }       
      return sb.toString();
    }

  • 0
    B

    this is why OP got my vote:

        public String originalDigits(String s) {
            
            int[] count = new int[26];
            int[] ret = new int[10];
            String[] word = {"zero","one","two","three","four","five","six","seven","eight","nine"};
            
            //count number of zero by char z
            for (char c : s.toCharArray())
                count[c - 'a']++;
    
            ret[0] = count['z' - 'a'];//z is unquely representation zero
            ret[2] = count['w' - 'a'];//w is unquely representation two
            ret[4] = count['u' - 'a'];
            ret[6] = count['x' - 'a'];
            ret[8] = count['g' - 'a'];
            
            //remove word 0, 2, 4, 6, 8 from string s
            for (int i = 0; i < 10; i++)
                for (char c : word[i].toCharArray())
                    count[c - 'a'] -= ret[i];
            
            //now 1, 3, 5, 7 can be uniquely identified by certain letters
            ret[1] = count['o' - 'a'];
            ret[3] = count['t' - 'a'];
            ret[5] = count['f' - 'a'];
            ret[7] = count['s' - 'a'];
    
            //remove word 1, 3, 5, 7 from string s
            for (int i = 1; i <= 7; i = i + 2)
                for (char c : word[i].toCharArray())
                    count[c - 'a'] -= ret[i];
            
            //what is left is 9
            ret[9] = count['i' - 'a'];
            
            StringBuffer sb = new StringBuffer();
            
            for (int i = 0; i < 10; i++)
                for (int j = 0; j < ret[i]; j++)
                    sb.append(i);
                    
            return sb.toString();
    
        }
    

  • 1

    @markieff Agree! Once we understand this brilliant idea, we can figure out this "unique level" on our own. Thanks!


  • 0
    S

    Similar idea. This is actually a mathematical problem. We want to figure out the number of digits, 0 - 9, that is, we have ten unknowns. Then according the letters of each English number and the total number of each letter in the given string, we can list 15 equations (because only 15 letters may appear in the English words for 0 to 9).
    In conclusion, we have 15 equations and 10 unknowns and then we can solve it. The codes are just telling how to solve these linear equations.

    class Solution(object):
        def originalDigits(self, s):
            """
            :type s: str
            :rtype: str
            """
            def index(c):
                return ord(c) - ord('a')
            # count the frequency of each letter
            letters_count = [0] * 26
            for c in s:
                letters_count[index(c)] += 1
            
            digits_count = [0] * 10
            digits_count[0] = letters_count[index('z')]
            digits_count[6] = letters_count[index('x')]
            digits_count[2] = letters_count[index('w')]
            digits_count[4] = letters_count[index('u')]
            digits_count[8] = letters_count[index('g')]
            digits_count[5] = letters_count[index('f')] - digits_count[4]
            digits_count[3] = letters_count[index('h')] - digits_count[8]
            digits_count[7] = letters_count[index('s')] - digits_count[6]
            digits_count[9] = letters_count[index('i')] - digits_count[5] - digits_count[6] - digits_count[8]
            digits_count[1] = letters_count[index('n')] - digits_count[7] - 2*digits_count[9]
            
            l = []
            for d, c in enumerate(digits_count):
                for _ in range(c):
                    l.append(str(d))
            return ''.join(l)

Log in to reply
 

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