numbers-at-most-n-given-digit-set.cpp

// Time:  O(logn)
// Space: O(logn)

class Solution {
public:
    int atMostNGivenDigitSet(vector<string>& D, int N) {
        string str_N = to_string(N);
        unordered_set<string> set_D(D.cbegin(), D.cend());
        int result = 0;
        for (int i = 1 ; i < str_N.length() ; ++i) {
            result += pow(D.size(), i);  // x, xx, xxx
        }
        int i = 0;
        // assume N = 1234, D = 1, 2, 3, 4
        for (i = 0 ; i < str_N.length() ; ++i) {
            for (const auto& d : D) {
                if (d[0] < str_N[i]) {
                    // 11xx; 121x, 122x; 1231, 1232, 1233;
                    result += pow(D.size(), str_N.length() - i - 1);
                } else {
                    break;
                }
            }
            if (!set_D.count(string(1, str_N[i]))) {
                break;
            }
        }               
        return result + int(i == str_N.length());  // 1234
    }
};