Two Strings Are Anagrams

Question

  1. Write a method anagram(s,t) to decide if two strings are anagrams or not.
  3. Example
  4. Given s="abcd", t="dcab", return true.
  6. Challenge
  7. O(n) time, O(1) extra space

題解1 - hashmap 統計字頻

判斷兩個字串是否互為變位詞，若區分大小寫，考慮空白字符時，直接來理解可以認為兩個字串的擁有各不同字符的數量相同。對於比較字符數量的問題常用的方法為遍歷兩個字串，統計其中各字符出現的頻次，若不等則返回false. 有很多簡單字串類面試題都是此題的變形題。

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param s: The first string
  5.      * @param t: The second string
  6.      * @return true or false
  7.      */
  8.     bool anagram(string s, string t) {
  9.         if (s.empty() || t.empty()) {
  10.             return false;
  11.         }
  12.         if (s.size() != t.size()) {
  13.             return false;
  14.         }
  16.         int letterCount[256] = {0};
  18.         for (int i = 0; i != s.size(); ++i) {
  19.             ++letterCount[s[i]];
  20.             --letterCount[t[i]];
  21.         }
  22.         for (int i = 0; i != t.size(); ++i) {
  23.             if (letterCount[t[i]] != 0) {
  24.                 return false;
  25.             }
  26.         }
  28.         return true;
  29.     }
  30. };

源碼分析

  1. 兩個字串長度不等時必不可能為變位詞(需要注意題目條件靈活處理)。
  2. 初始化含有256個字符的計數器陣列。
  3. 對字串 s 自增，字串 t 遞減，再次遍歷判斷letterCount陣列的值，小於0時返回false.

在字串長度較長(大於所有可能的字符數)時，還可對第二個for循環做進一步優化，即t.size() > 256時，使用256替代t.size(), 使用i替代t[i].

複雜度分析

兩次遍歷字串，時間複雜度最壞情況下為 O(2n), 使用了額外的陣列，空間複雜度 O(256).

題解2 - 排序字串

另一直接的解法是對字串先排序，若排序後的字串內容相同，則其互為變位詞。題解1中使用 hashmap 的方法對於比較兩個字串是否互為變位詞十分有效，但是在比較多個字串時，使用 hashmap 的方法複雜度則較高。

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param s: The first string
  5.      * @param b: The second string
  6.      * @return true or false
  7.      */
  8.     bool anagram(string s, string t) {
  9.         if (s.empty() || t.empty()) {
  10.             return false;
  11.         }
  12.         if (s.size() != t.size()) {
  13.             return false;
  14.         }
  16.         sort(s.begin(), s.end());
  17.         sort(t.begin(), t.end());
  19.         if (s == t) {
  20.             return true;
  21.         } else {
  22.             return false;
  23.         }
  24.     }
  25. };

源碼分析

對字串 s 和 t 分別排序，而後比較是否含相同內容。對字串排序時可以採用先統計字頻再組裝成排序後的字串，效率更高一點。

複雜度分析

C++的 STL 中 sort 的時間複雜度介於 O(n) 和 O(n^2)之間，判斷s == t時間複雜度最壞為 O(n).

Reference

  • CC150 Chapter 9.1 中文版 p109