確定兩個字符串是否彼此排列的程序的時間複雜度

我已經編寫了一個程序來確定兩個字符串是否是彼此的排列。我正在嘗試使用哈希表來實現。這裏是我的代碼：確定兩個字符串是否彼此排列的程序的時間複雜度

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）。我想不出一個不涉及使用嵌套循環的算法。有沒有更快的方法來做到這一點使用哈希表？

來源

2016-12-30 CheetahBongos

爲什麼你需要使用一個哈希表？對字符串中的字符進行排序，如果兩個排序的字符串相同，則一個是另一個排列。 –

@latedeveloper排序將是n log（n），而這可以在線性時間完成。 –

我試圖用散列表更好，所以我想嘗試使用這個程序。 – CheetahBongos

是的。

#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'; 
}

來源

2016-12-30 21:49:44

爲什麼要用哈希表 - 爲什麼不簡單地使用數組？ –

@latedeveloper對於短字符串，哈希表可能會更快（因爲我們不需要初始化長度爲256的數組），所以更好地推廣到Unicode（因爲表中有一百萬個條目），但主要是因爲OP請求它。 –

a）然而，我們確實需要初始化散列表。 b）YAGNI，c）好點。 –

TL; DR我想測試解決方案（包括我自己）：大衛的基於地圖的答案執行體面的好（這是一個很大的通用），其基於陣列的解決方案表現非常好，我自己的解決方案是隻是稍微快一點，但可讀性稍差（可能不值得）。

誠實地說，當我看到這個時，我無法相信大衛對無序地圖的回答可能具有最低的時間複雜度。（很可能在理論上，但不是在實踐中）

我通常用C編寫，所以我不知道C++提供的這些數據結構的優化類型或它們在現實生活中的表現如何。所以我決定測試它。

因此我開始了我的i7的一些測試，以測試各種解決方案的性能，有一些輕微的改動（source code here）

我跑的程序1 100000次）2組的排列和2）2種不同也就是說

的成績排在如下：

PERM original 
====================== 
PERMUTATIONS OF SAME WORD 
real 104.73 
user 104.61 
sys 0.06 

DIFFERENT WORDS 
real 104.24 
user 104.16 
sys 0.02 

PERM David map 
====================== 
PERMUTATIONS OF SAME WORD 
real 2.46 
user 2.44 
sys 0.00 

DIFFERENT WORDS 
real 2.45 
user 2.42 
sys 0.02 

PERM David array 
====================== 
PERMUTATIONS OF SAME WORD 
real 0.15 
user 0.14 
sys 0.00 

DIFFERENT WORDS 
real 0.14 
user 0.14 
sys 0.00 

PERM Me 
====================== 
PERMUTATIONS OF SAME WORD 
real 0.13 
user 0.13 
sys 0.00 

DIFFERENT WORDS 
real 0.14 
user 0.12 
sys 0.01

來源

2016-12-31 00:08:12

我想我的馬最後一次進入:(這是驚人的嵌套for循環可以導致多大的差異。非常有趣 – CheetahBongos

確定兩個字符串是否彼此排列的程序的時間複雜度

回答

相關問題