Fun fact


  • 17

    The even digits all have a unique letter while the odd digits all don't:

    zero: Only digit with z
    two: Only digit with w
    four: Only digit with u
    six: Only digit with x
    eight: Only digit with g

    The odd ones for easy looking, each one's letters all also appear in other digit words:
    one, three, five, seven, nine


  • 3
    Y

    @StefanPochmann Exactly! And here is my code based on this idea

    
    class Solution(object):
        def originalDigits(self, s):
            """
            :type s: str
            :rtype: str
            """
            words=[['z','zero',0],['x','six',6],['s','seven',7],['v','five',5],\
                    ['g','eight',8],['f','four',4],['h','three',3],\
                    ['w','two',2],['o','one',1],['i','nine',9]]
            d={}
            for c in s:
                if c not in d:
                    d[c]=0
                d[c]+=1
            res=[]
            for k,word,num in words:
                if k in d:
                    v=d[k]
                    for c in word:
                        d[c]-=v
                        if d[c]==0:
                            del d[c]
                    res.append(str(num)*v)
            return ''.join(sorted(res))
    

  • 3

    @yadongwen Hmm, I don't see what your solution has to do with it. In fact, I don't see at all how to actually make use of it. Except maybe if you have to solve this problem again, it might save a little time to remember that you can do the even digits first. But you're not even doing that...

    I like your sorting at the end, though. Here's a variation:

    def originalDigits(self, s):
        d = collections.Counter(s)
        res = []
        for x in '0eroz 6six 7evens 5fiev 8eihtg 4ourf 3treeh 2tow 1neo 9nnei'.split():
            res.append(x[0] * d[x[-1]])
            for c in x:
                d[c] -= d[x[-1]]
        return ''.join(sorted(res))

  • 0
    R

    Very nice catch! Add some modification which won't need sorting.

    class Solution(object):
        def originalDigits(self, s):
            """
            :type s: str
            :rtype: str
            """
            d = collections.Counter(s)
            ans = [0] * 10
            for x in '0eroz 2tow 4foru 6six 8eihtg 1eno 3theer 5ivef 7evens 9nnei'.split():
                ans[int(x[0])] = d[x[-1]]
                for c in x:
                    d[c] -= d[x[-1]]
            return ''.join([str(i)*ans[i] for i in range(10)])
    

  • 0

    @ra1den Well the sorting is sorting only ten strings, and they all differ already at the very first letter, so it's very fast.


  • 1

    @StefanPochmann I think what he means is that he is searching for the letters in the spelling of a number starting with "zero", then "six" and so on utilizing the fact that if "z", "e", "r", "o" is found it necessarily means those belong to a "zero". Once all zeros are found and reduced from the counting array he moves onto "six" and so on. By searching in the order he has suggested he will not get any false positives. Here is another take on that logic

        public string OriginalDigits(string s) 
        {
            int[] counts = new int[26];
            for (int i = 0; i < s.Length; i++)
            {
                counts[s[i] - 'a']++;
            }
            
            // order them such that finding all characters in an entry uniquely identifies that entry
            Tuple<string, int>[] numberLetters = new Tuple<string, int>[]
            {
                new Tuple<string,int>("zero", 0),
                new Tuple<string,int>("six", 6),
                new Tuple<string,int>("two", 2),
                new Tuple<string,int>("eight", 8),
                new Tuple<string,int>("four", 4),
                new Tuple<string,int>("three", 3),
                new Tuple<string,int>("five", 5),
                new Tuple<string,int>("seven", 7),
                new Tuple<string,int>("one", 1),
                new Tuple<string,int>("nine", 9),
            };
            
            List<int> list = new List<int>();
            for (int i = 0; i <= 9; i++)
            {
                bool all = true;
                while (all)
                {
                    foreach (char c in numberLetters[i].Item1)
                    {
                        if (counts[c - 'a'] == 0)
                        {
                            all = false;
                            break;
                        }
                    }
                    if (all)
                    {
                        foreach (char c in numberLetters[i].Item1)
                        {
                            counts[c - 'a']--;
                        }
                        list.Add(numberLetters[i].Item2);
                    }
                }
            }
            
            StringBuilder sb = new StringBuilder();
            foreach (int x in list.OrderBy(x => x)) { sb.Append(x.ToString()); }
            return sb.ToString();
        }
    

  • 0
    This post is deleted!

  • 1

    @jdrogin Yeah, but that's how pretty much everybody (including me) had already solved it (my topic here is really just a fun additional fact). Oh well, I guess maybe yadongwen hadn't thought of it before and did get the idea after seeing my observation about the evens. Then it did make sense to reply here with that, although the "based on this idea" still feels like credit I don't deserve :-)

    (If you saw my now deleted answer: I thought you were replying to my reply to @ra1den.)


  • -1
    Z
    This post is deleted!

  • 0
    Z

    Hi! My solution is also based on that idea. Order of spells matters. First off we search for digits with unique letters. I met similar problem in Google Code Jam 2016.

    public class Solution {
        String [] spells = {"zero","two","six","eight","seven","three","four","five","nine","one"};
        int [] nums = {0,2,6,8,7,3,4,5,9,1};
        public String originalDigits(String s) {
            StringBuilder res=  new StringBuilder();
            if(s.isEmpty()) return res.toString();
            List<Integer> discovered = new ArrayList<>();
            int [] charFreq = getCharFreq(s);
            for(int i = 0;i<spells.length;i++){
                while(isDiscoverable(charFreq, spells[i])){
                    discovered.add(nums[i]);
                }
            }
            Collections.sort(discovered);
            for(Integer num:discovered){
                res.append(num);
            }
            return res.toString();
        }
        
        private int [] getCharFreq(String s){
            int [] res = new int[26];
            for(int i = 0;i<s.length();i++){
                res[s.charAt(i)-'a']++;
            }
            return res;
        }
        
        private boolean isDiscoverable(int [] charFreq, String spell){
            Stack<Integer> st = new Stack<>();
            st.push(0);
            while(!st.isEmpty()){
                int pos = st.peek();
                if(pos == spell.length()) return true;
                int i = spell.charAt(pos)-'a';
                if(charFreq[i] == 0) {
                    st.pop();
                    while(!st.isEmpty()){
                        charFreq[spell.charAt(st.pop())-'a']++;
                    }
                    return false;
                }
                charFreq[i]--;
                st.push(pos+1);
            }
            return false;
        }
    }

Log in to reply
 

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