求解变位词（Anagram）高效方案及字母版实现技术问询

Hey there! Let's tackle your two questions: optimizing your number anagram generator and implementing letter-based anagram generation. Let's dive in!

First, let's look at the limitations of your current code:

• It traverses every number between your input and its reverse (e.g., 1234 to 4321) and checks each one for being an anagram. For longer numbers (like 8 digits), this means checking tens of thousands of values—super inefficient.
• The isAnagram function uses two separate arrays, which is unnecessary and adds minor overhead.

Better Approach: Generate Permutations Directly #

Anagrams of a number are just unique permutations of its digits. Instead of checking every number, we can generate these permutations directly, then convert them back to integers. This cuts down the work drastically (e.g., 4 digits have only 24 permutations vs. 3087 numbers to check in your original code).

Here's the optimized code:

#include <iostream>
#include <algorithm>
#include <string>
#include <set>

using namespace std;

int main() {
    int num;
    cin >> num;
    string digit_str = to_string(num);
    set<string> unique_perms; // Automatically handles duplicate digits (e.g., input 112)

    // Sort first to ensure next_permutation generates all valid permutations
    sort(digit_str.begin(), digit_str.end());
    do {
        unique_perms.insert(digit_str);
    } while (next_permutation(digit_str.begin(), digit_str.end()));

    // Output valid anagrams (skip permutations with leading zeros)
    for (const string& perm : unique_perms) {
        if (perm[0] != '0') {
            cout << stoi(perm) << endl;
        }
    }

    return 0;
}

Quick Optimization for Your Original isAnagram (If You Still Want to Use Traversal) #

If you prefer to keep the traversal approach, you can simplify the anagram check to use a single array instead of two:

bool isAnagram(int number, int number2) {
    int digit_counts[10] = {0};
    int total_digits = 0;

    // Count digits from first number
    while (number > 0) {
        digit_counts[number % 10]++;
        number /= 10;
        total_digits++;
    }

    // Subtract digits from second number
    while (number2 > 0) {
        digit_counts[number2 % 10]--;
        number2 /= 10;
        total_digits--;
    }

    // If digit counts don't match, return false immediately
    if (total_digits != 0) return false;

    // Verify all digit counts are zero
    for (int i = 0; i < 10; i++) {
        if (digit_counts[i] != 0) return false;
    }
    return true;
}

Letter anagrams work almost the same way—they're just unique permutations of the input string. The key difference is we don't have to worry about leading zeros, and we need to handle duplicate characters (e.g., input "aab" should only generate 3 unique anagrams).

Working Code Example #

#include <iostream>
#include <algorithm>
#include <string>
#include <set>

using namespace std;

void generateLetterAnagrams(string input) {
    set<string> unique_anagrams;
    sort(input.begin(), input.end());

    // Generate all unique permutations
    do {
        unique_anagrams.insert(input);
    } while (next_permutation(input.begin(), input.end()));

    // Print results
    cout << "Unique letter anagrams:\n";
    for (const string& anagram : unique_anagrams) {
        cout << anagram << "\n";
    }
}

int main() {
    string user_input;
    cout << "Enter a string: ";
    cin >> user_input;
    generateLetterAnagrams(user_input);
    return 0;
}

Notes: #

• The set automatically removes duplicate permutations, which is crucial if your input has repeated characters.
• next_permutation generates permutations in lexicographical order, so sorting the input first ensures we don't miss any valid permutations.

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