如何用C++实现字符串仅含指定合法字符的校验？

Hey there! Let's break down your current approach and explore some better, more efficient ways to validate if a string only contains characters from a given charset.

First, Let's Talk About Your Current Implementation #

Your initial idea has a couple of critical issues that prevent it from working correctly:

• Invalid std::replace usage: The third argument to std::replace must be a valid char, but '' is an empty character literal which isn't allowed in C++. This code won't even compile.
• Unwanted side effect: You're modifying the original input string (myString), which callers almost certainly don't expect.
• Inefficiency: Each std::replace call scans the entire target string, leading to a time complexity of O(M*N) where M is the charset length and N is the target string length.

Better Solutions #

1. Simple & Readable: std::all_of + std::string::find #

This approach is concise, avoids modifying the input, and is easy to follow. We check every character in the target string to see if it exists in the charset.

#include <string>
#include <algorithm>

bool isValidString(const std::string& target, const std::string& charset) {
    return std::all_of(target.begin(), target.end(),
        [&charset](char c) {
            return charset.find(c) != std::string::npos;
        });
}

// Example usage:
int main() {
    const std::string charset = "abc123";
    std::string myString_1 = "bbbac1"; // Returns true
    std::string myString_3 = "xxxxxx"; // Returns false
    
    bool valid1 = isValidString(myString_1, charset);
    bool valid3 = isValidString(myString_3, charset);
    return 0;
}

Pros: No side effects, minimal code, works for any charset.
Cons: std::string::find is O(M) per character, so overall O(N*M) time—perfect for small charsets or infrequent checks.

2. Efficient for Frequent Checks: std::unordered_set #

If you need to validate multiple strings against the same charset, preloading the charset into an unordered set gives O(1) average lookup time, cutting overall complexity to O(M + N).

#include <string>
#include <algorithm>
#include <unordered_set>

bool isValidString(const std::string& target, const std::unordered_set<char>& charsetSet) {
    // For C++20+, use charsetSet.contains(c) for cleaner code
    return std::all_of(target.begin(), target.end(),
        [&charsetSet](char c) {
            return charsetSet.find(c) != charsetSet.end();
        });
}

// Example usage:
int main() {
    const std::string charset = "abc123";
    std::unordered_set<char> charsetSet(charset.begin(), charset.end());
    
    std::string myString_2 = "bbbac132aacc"; // Returns true
    std::string myString_4 = "bbbac12533cc"; // Returns false
    
    bool valid2 = isValidString(myString_2, charsetSet);
    bool valid4 = isValidString(myString_4, charsetSet);
    return 0;
}

Pros: Fast lookups, ideal for repeated validation with the same charset.
Cons: Slightly more setup, has minor overhead from the hash table.

3. Blazing Fast for ASCII Chars: Boolean Array #

For ASCII characters (0-255), a simple boolean array provides the fastest possible lookup with zero overhead.

#include <string>

bool isValidString(const std::string& target, const std::string& charset) {
    bool allowed[256] = {false}; // Initialize all to false
    
    // Mark allowed characters
    for (char c : charset) {
        allowed[static_cast<unsigned char>(c)] = true;
    }
    
    // Check each character in target
    for (char c : target) {
        if (!allowed[static_cast<unsigned char>(c)]) {
            return false;
        }
    }
    return true;
}

// Example usage:
int main() {
    const std::string charset = "abc123";
    std::string myString_1 = "bbbac1"; // true
    std::string myString_4 = "bbbac12533cc"; // false
    
    bool valid1 = isValidString(myString_1, charset);
    bool valid4 = isValidString(myString_4, charset);
    return 0;
}

Pros: O(M + N) time, minimal memory usage, fastest performance for ASCII.
Cons: Only works for characters in the ASCII range (0-255).

Which One Should You Choose? #

• Go with the first option if you want simplicity and don't need maximum performance.
• Use the unordered set if you're validating many strings against the same charset.
• Pick the boolean array if you're working with ASCII characters and need top-tier speed.

内容的提问来源于stack exchange，提问作者user3596335