求优化字符串组合含0-9全数字的配对统计方案性能

Hey there! Let's tackle this problem step by step—first we'll break down the flaws in a basic implementation, then jump into a way faster approach using bitmasking that'll handle large input sizes with ease.

Common Issues with Basic Implementations #

If your current solution follows the "brute force" playbook, it's likely suffering from these bottlenecks:

• O(n²) Pair Enumeration: Checking every possible pair of strings directly means if you have 10,000 tickets, you're doing 100 million operations—way too slow for large datasets.
• Redundant Character Scans: For each pair, you're re-scanning both strings to check if all digits 0-9 are present. This repeats work you could do once upfront.
• No Caching of Digit Presence: You're recalculating which digits each string contains every time it's part of a pair, wasting cycles on redundant computations.

Performance-Optimized Solution: Bitmasking #

Since we only care about 10 unique digits (0-9), we can represent each string's digit coverage with a 10-bit integer mask—each bit corresponds to whether a digit is present (1 = present, 0 = missing). This lets us turn string comparisons into fast bitwise operations.

Step 1: Precompute Bitmasks for All Strings #

First, convert every ticket string into its corresponding bitmask:

private static int getBitmask(String s) {
    int mask = 0;
    for (char c : s.toCharArray()) {
        int digit = c - '0';
        mask |= 1 << digit; // Set the digit's bit to 1
    }
    return mask;
}

This runs in O(total number of characters across all tickets) time—way more efficient than re-scanning strings for every pair.

Step 2: Count Mask Frequencies #

Since there are only 2¹⁰ = 1024 possible unique masks, we can use a small array to count how many times each mask appears:

int[] maskCount = new int[1024];
for (String ticket : tickets) {
    int mask = getBitmask(ticket);
    maskCount[mask]++;
}

This is O(n) time, where n is the number of tickets.

Step 3: Calculate Valid Pairs #

Now we need to find all pairs of masks where their bitwise OR equals 0b1111111111 (decimal 1023)—meaning together they cover all digits. To avoid double-counting pairs:

static long getNumberOfValidPairs(String[] tickets) {
    int[] maskCount = new int[1024];
    for (String ticket : tickets) {
        int mask = 0;
        for (char c : ticket.toCharArray()) {
            mask |= 1 << (c - '0');
        }
        maskCount[mask]++;
    }

    long validPairs = 0;
    int fullMask = 0b1111111111; // 1023

    for (int mask1 = 0; mask1 < 1024; mask1++) {
        if (maskCount[mask1] == 0) continue;

        int requiredMask = fullMask ^ mask1; // Mask that covers what mask1 is missing

        if (mask1 == requiredMask) {
            // Choose 2 from count[mask1] (same mask pairs)
            validPairs += (long) maskCount[mask1] * (maskCount[mask1] - 1) / 2;
        } else if (mask1 < requiredMask) {
            // Multiply counts of mask1 and requiredMask to get cross pairs
            validPairs += (long) maskCount[mask1] * maskCount[requiredMask];
        }
    }

    return validPairs;
}

This final loop runs in O(1) time (since 1024 is a fixed constant), making the entire solution's time complexity O(total_chars + n)—a massive improvement over brute force.

Why This Works #

• Bitwise operations are lightning-fast (single CPU cycles).
• We eliminate redundant work by precomputing masks once.
• The fixed-size frequency array is far faster than a hash map for this use case.

Example Walkthrough #

Using your sample input ["012345","6789","34567"]:

1. Masks:
   • "012345" → 0b000000111111 (63)
   • "6789" → 0b1111000000 (960)
   • "34567" → 0b00011111000 (120)
2. Mask counts: count[63] = 1, count[960] = 1, count[120] = 1
3. Valid pairs: Only 63 | 960 = 1023, so validPairs = 1*1 = 1—matches your expected result.

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