Untitled
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); } };