1.4.cc

// Time: n * log(n) 
// Space: depend on sort() implementation (most recent sgi implementation use Introsort, which is Space: log(n))
bool IsAnagram(string s1, string s2) {
  sort(s1.begin(), s1.end());
  sort(s2.begin(), s2.end());
  return s1 == s2;
}

// Time: n
// Space: 256
bool IsAnagram1(string s1, string s2) {
  int letters[256] = {0};
  for (size_t i = 0; i < s1.size(); ++i) 
    letters[s1[i]]++;
  
  for (size_t i = 0; i < s2.size(); ++i) {
    letters[s2[i]]--;
    if (letters[s2[i]] < 0) return false;
  }

  for (size_t i = 0; i < 256; ++i) 
    if (letters[i] != 0) return false;
 
  return true;
}

//Time: n
//Space: 256
//The implementation by the CCI book, which trades code complexity for time
//it make sense only when s2 is extremely long LoL, since the time saved by getting rid of the third "for" loop (256) is negligible
bool IsAnagram2(string s1, string s2) {
  int letters[256] = {0};
  int unique_chars = 0;
  for (size_t i = 0; i < s1.size(); ++i) {
    if (letters[s1[i]] == 0) unique_chars++;
    letters[s1[i]]++;
  }
  
  for (size_t i = 0; i < s2.size(); ++i) {
    letters[s2[i]]--;
    if (letters[s2[i]] < 0) return false;
    else if (letters[s2[i]] == 0) {
      unique_chars--;
      if (unique_chars == 0) return i == s2.size() - 1;
    }
  }
}