c++ - 确定两个字符串是否互为排列的程序的时间复杂度

Question

我编写了一个程序来确定两个字符串是否是彼此的排列。我正在尝试使用哈希表来这样做。这是我的代码:

bool permutation(string word1, string word2) {

    unordered_map<char, int> myMap1;
    unordered_map<char, int> myMap2;
    int count1 = 0;
    int count2 = 0;

    if (word1.length() == word2.length()) {
        for (int i = 0; i < word1.length(); i++) {
            count1++;
            count2++;
            for (int j = 0; j < word1.length(); j++) {
                if (word1[i] == word1[j] && myMap1.find(word1[i]) == myMap1.end()) {
                    count1++;
                }
                if (word2[i] == word2[j] && myMap2.find(word1[i]) == myMap2.end()) {
                    count2++;
                }
            }
            myMap1.insert({word1[i], count1});
            myMap2.insert({word2[i], count2});
        }
    }
    else {
        return false;
    }
    return (myMap1.size() == myMap2.size());
}

int main() {

    string word1;
    string word2;
    getline(cin, word1);
    getline(cin, word2);

    bool result = permutation(word1, word2);

    return 0;
}

我相信上面代码的时间复杂度是 O(n^2)。我想不出不涉及使用嵌套循环的算法。有没有更快的方法使用哈希表来做到这一点？

Answer 1

是的。

#include <climits>
#include <iostream>
#include <unordered_map>

namespace {

bool permutation(const std::string& word1, const std::string& word2) {
  std::unordered_map<char, std::size_t> freqdiff;
  // alternatively, std::size_t freqdiff[UCHAR_MAX + 1] = {};
  for (char c : word1) {
    // alternatively, freqdiff[(unsigned char)c]++;
    freqdiff[c]++;
  }
  for (char c : word2) {
    // alternatively, freqdiff[(unsigned char)c]--;
    freqdiff[c]--;
  }
  for (auto i : freqdiff) {
    // alternatively, i != 0
    if (i.second != 0) {
      return false;
    }
  }
  return true;
}

bool permutation_with_array(const std::string& word1,
                            const std::string& word2) {
  std::size_t freqdiff[UCHAR_MAX + 1] = {};
  for (char c : word1) {
    freqdiff[static_cast<unsigned char>(c)]++;
  }
  for (char c : word2) {
    freqdiff[static_cast<unsigned char>(c)]--;
  }
  for (std::size_t i : freqdiff) {
    if (i != 0) {
      return false;
    }
  }
  return true;
}
}

int main() {
  std::string word1;
  std::string word2;
  std::getline(std::cin, word1);
  std::getline(std::cin, word2);
  std::cout << permutation(word1, word2) << '\n';
  std::cout << permutation_with_array(word1, word2) << '\n';
}