Question

Source

• lintcode: (158) Two Strings Are Anagrams

Write a method anagram(s,t) to decide if two strings are anagrams or not.

Example
Given s="abcd", t="dcab", return true.

Challenge
O(n) time, O(1) extra space

题解 1 - hashmap 统计字频

判断两个字符串是否互为变位词，若区分大小写，考虑空白字符时，直接来理解可以认为两个字符串的拥有各不同字符的数量相同。对于比较字符数量的问题常用的方法为遍历两个字符串，统计其中各字符出现的频次，若不等则返回 false . 有很多简单字符串类面试题都是此题的变形题。

Python

class Solution:
  """
  @param s: The first string
  @param b: The second string
  @return true or false
  """
  def anagram(self, s, t):
    return collections.Counter(s) == collections.Counter(t)

C++

class Solution {
public:
  /**
   * @param s: The first string
   * @param b: The second string
   * @return true or false
   */
  bool anagram(string s, string t) {
    if (s.empty() || t.empty()) {
      return false;
    }
    if (s.size() != t.size()) {
      return false;
    }

    int letterCount[256] = {0};

    for (int i = 0; i != s.size(); ++i) {
      ++letterCount[s[i]];
      --letterCount[t[i]];
    }
    for (int i = 0; i != t.size(); ++i) {
      if (letterCount[t[i]] != 0) {
        return false;
      }
    }

    return true;
  }
};

源码分析

1. 两个字符串长度不等时必不可能为变位词（需要注意题目条件灵活处理)。
2. 初始化含有 256 个字符的计数器数组。
3. 对字符串 s 自增，字符串 t 递减，再次遍历判断 letterCount 数组的值，小于 0 时返回 false .

在字符串长度较长（大于所有可能的字符数) 时，还可对第二个 for 循环做进一步优化，即 t.size() > 256 时，使用 256 替代 t.size() , 使用 i 替代 t[i] .

复杂度分析

两次遍历字符串，时间复杂度最坏情况下为 O(n)O(n)O(n), 使用了额外的数组，空间复杂度 O(1)O(1)O(1).

题解 2 - 排序字符串

另一直接的解法是对字符串先排序，若排序后的字符串内容相同，则其互为变位词。题解 1 中使用 hashmap 的方法对于比较两个字符串是否互为变位词十分有效，但是在比较多个字符串时，使用 hashmap 的方法复杂度则较高。

Python

class Solution:
  """
  @param s: The first string
  @param b: The second string
  @return true or false
  """
  def anagram(self, s, t):
    return sorted(s) == sorted(t)

C++

class Solution {
public:
  /**
   * @param s: The first string
   * @param b: The second string
   * @return true or false
   */
  bool anagram(string s, string t) {
    if (s.empty() || t.empty()) {
      return false;
    }
    if (s.size() != t.size()) {
      return false;
    }

    sort(s.begin(), s.end());
    sort(t.begin(), t.end());

    if (s == t) {
      return true;
    } else {
      return false;
    }
  }
};

源码分析

对字符串 s 和 t 分别排序，而后比较是否含相同内容。对字符串排序时可以采用先统计字频再组装成排序后的字符串，效率更高一点。

复杂度分析

C++的 STL 中 sort 的时间复杂度介于 O(n)O(n)O(n) 和 O(n2)O(n^2)O(n2) 之间，判断 s == t 时间复杂度最坏为 O(n)O(n)O(n).

Reference

• CC150 Chapter 9.1 中文版 p109