Most Efficient way to search if a string contain all numbers from 0 to 9 at least once?

Question

bool IsWin(string A, string B)
{
    vector<int> vec = {0,1,2,3,4,5,6,7,8,9};

    for(long int i=0;i<A.length();i++){
        vec[A[i]-'0'] = 11;
    }

    if(IsArray(vec)){    //IsArray(vec) It just checks whether all elements are 11.
        return true;
    }

    for(long int i=0;i<B.length();i++){
        vec[B[i]-'0'] = 11;
    }

    return IsArray(Array);
}

Answer 1

Seems like the obvious way would be something like this:

bool has_all_digits(std::string const &input) { 
    std::vector<char> present(10, 0);
    for (auto c : input)
        present[c - '0' ] = 1;

    return std::find(present.begin(), present.end(), 0) == present.end();
}

Answer 2

In this case std::bitset is probably the most efficient way to solve this.

bool check(string s){
    std::bitset<10> digits;
    int digitCounter = 0;
    int index;

    for (char c : s){
        if (std::isdigit(c)){
            index = c - '0';

            if (!digits[index]){
                digitCounter++;
                digits[index] = true;

                if (digitCounter == 10)
                    return true;
            }       
        }
    }

    return false;
}

Answer 3

This will have out of range exceptions for vec if A or B contains anything beside digits. Between the loops vec needs to be reinitialised. Further the last line should be IsArray(vec). And why not use a vector<bool> vec?

Before you care for efficiency the algorithm should work and be exception safe.

Answer 4

Any talk about performance is meaningless without benchmarking. So you need to measure and then measure some more.

With that in mind here is a version that is optimized for long strings with dense digits, i.e. that have a high probability to contain all the digits in a small substring. The function will exits as soon as it found all the digits and will not continue to the rest of the string:

auto has_all_digits(const std::string& str) -> bool
{
    std::array<int, 10> digits = {};
    int num_digits = 0;

    for (char ch : str)
    {
        if (!is_digit(ch))
            continue;

        // here is a cool branchless trick
        // to count unique digits

        int x = 1;
        std::swap(digits[ch - '0'], x); // put 1 to digits and get the old value in x
        num_digits += 1 - x; // increment if the old value was 0

        if (num_digits == 10)
            return true;
    }

    return false;    
}

Again, don't forget to measure and see if this algorithm is indeed eficient for your use case.