Simply enumerate them one by one, from lowest. (Java)


  • 0
    T
    static char[] LO = {'0', '1', 'a', 'd', 'g', 'j', 'm', 'p', 't', 'w'};
    static char[] HI = {'0', '1', 'c', 'f', 'i', 'l', 'o', 's', 'v', 'z'};
    
    public List<String> letterCombinations(String digits) {
    
        if(digits.isEmpty()) // ?
            return Collections.emptyList();
    
        int TOTAL=1;
        char[] lo = new char[digits.length()];
        char[] hi = new char[digits.length()];
        for(int i=0; i<digits.length(); i++)
        {
            int d = digits.charAt(i) - '0';
            lo[i] = LO[d];
            hi[i] = HI[d];
            TOTAL *= (hi[i]-lo[i]+1);
        }
        ArrayList<String> list = new ArrayList<>(TOTAL);
    
        char[] buf = Arrays.copyOf(lo, lo.length);
        while(list.size()<TOTAL)
        {
            list.add(new String(buf));
    
            // increment
            for(int i=buf.length-1; i>=0; i--)
            {
                if(++buf[i]<=hi[i])
                    break;
                // carry
                buf[i]=lo[i];
            }
        }
        return list;
    }

Log in to reply
 

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