Two Strings Are Anagrams

Tags: String, Cracking The Coding Interview, Easy

Question

Problem Statement

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

Clarification

What is Anagram?
- Two strings are anagram if they can be the same after change the order of
characters.

Example

Given s = "abcd", t = "dcab", return true.
Given s = "ab", t = "ab", return true.
Given s = "ab", t = "ac", return false.

Challenge **

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

题解1 - hashmap 统计字频

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

Python

  1. class Solution:
  2.     """
  3.     @param s: The first string
  4.     @param b: The second string
  5.     @return true or false
  6.     """
  7.     def anagram(self, s, t):
  8.         return collections.Counter(s) == collections.Counter(t)

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.         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. };

Java

  1. public class Solution {
  2.     /**
  3.      * @param s: The first string
  4.      * @param b: The second string
  5.      * @return true or false
  6.      */
  7.     public boolean anagram(String s, String t) {
  8.         if (s == null || t == null) return false;
  9.         if (s.length() != t.length()) return false;
  11.         final int CHAR_NUM = 256;
  12.         int[] letterCount = new int[CHAR_NUM];
  14.         for (int i = 0; i != s.length(); i++) {
  15.             letterCount[s.charAt(i)]++;
  16.             letterCount[t.charAt(i)]--;
  17.         }
  18.         for (int i = 0; i != CHAR_NUM; i++) {
  19.             if (letterCount[i] != 0) return false;
  20.         }
  22.         return true;
  23.     }
  24. };

源码分析

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

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

复杂度分析

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

题解2 - 排序字符串

另一直接的解法是对字符串先排序，若排序后的字符串内容相同，则其互为变位词。

Python

  1. class Solution:
  2.     """
  3.     @param s: The first string
  4.     @param b: The second string
  5.     @return true or false
  6.     """
  7.     def anagram(self, s, t):
  8.         return sorted(s) == sorted(t)

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. };

Java

  1. public class Solution {
  2.     /**
  3.      * @param s: The first string
  4.      * @param b: The second string
  5.      * @return true or false
  6.      */
  7.     public boolean anagram(String s, String t) {
  8.         if (s == null || t == null) return false;
  9.         if (s.length() != t.length()) return false;
  11.         char[] sChars = s.toCharArray();
  12.         char[] tChars = t.toCharArray();
  13.         Arrays.sort(sChars);
  14.         Arrays.sort(tChars);
  16.         for (int i = 0; i != s.length(); i++) {
  17.             if (sChars[i] != tChars[i]) return false;
  18.         }
  20.         return true;
  21.     }
  22. };

源码分析

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

复杂度分析

C++的 STL 中 sort 的时间复杂度介于 O(n) 和 O(n^2)之间，判断s == t时间复杂度最坏为 O(n). 可以看出此方法的时间复杂度相比题解1还是比较高的。Java 中字符串默认不可变，故空间复杂度为 O(n).

Reference

  • CC150 Chapter 9.1 中文版 p109