Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.1 kB
3
Indexable
Never
class Solution {
    
    int notUsedBefore(int bitMask, int possibleDigit){
        return (((1 << possibleDigit) & bitMask) == 0) ? true : false;
    }
    
    int markUsedDigit(int bitMask, int possibleDigit){
        if(possibleDigit == 0 && bitMask == 0)return bitMask;
        else{
            return ((1 << possibleDigit) | bitMask);
        }
    }
    
    bool findInMap(int index, bool isLast, int bitMask, 
                   unordered_map<int, unordered_map<bool, unordered_map<int, int>>> &dpMemo){
        if(
                dpMemo.find(index) != dpMemo.end() &&
                dpMemo[index].find(isLast) != dpMemo[index].end() &&
                dpMemo[index][isLast].find(bitMask) != dpMemo[index][isLast].end()
        ) return true;
        return false;
    }
    
    
    int countSpecialNumsDP(int index, bool isLast, int bitMask, string &strNum,
                          unordered_map<int, unordered_map<bool, unordered_map<int, int>>> &dpMemo){
        // if given index is not valid
        if(index == strNum.size())return dpMemo[index][isLast][bitMask] = (bitMask <= 1) ? 0: 1;  
        if(findInMap(index, isLast, bitMask, dpMemo))return dpMemo[index][isLast][bitMask];
        // Place possible digits at the given index, if valid
        int fromDigit = 0;
        int toDigit = (isLast == true) ? (strNum[index]-'0') : 9;
        int countNumbers = 0;
        for(int possibleDigit = fromDigit; possibleDigit <= toDigit; possibleDigit++){
            if(notUsedBefore(bitMask, possibleDigit)){
                int updatedBitMask = markUsedDigit(bitMask, possibleDigit);
                countNumbers += countSpecialNumsDP(index +1, (isLast && (possibleDigit == toDigit)), 
                                                   updatedBitMask, strNum, dpMemo);
            }
        }
        return dpMemo[index][isLast][bitMask] = countNumbers;
    }
    
    
public:
    int countSpecialNumbers(int n) {
        string strNum = to_string(n);
        unordered_map<int, unordered_map<bool, unordered_map<int, int>>> dpMemo;
        return countSpecialNumsDP(0, true, 0, strNum, dpMemo);
    }
};