Two Strings Are Anagrams

    Write a method 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.

    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

    Python

    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.         }
    11.         if (s.size() != t.size()) {
    12.             return false;
    13.         }
    17.         for (int i = 0; i != s.size(); ++i) {
    18.             ++letterCount[s[i]];
    19.             --letterCount[t[i]];
    20.         }
    21.         for (int i = 0; i != t.size(); ++i) {
    22.             if (letterCount[t[i]] != 0) {
    23.                 return false;
    24.             }
    25.         }
    27.         return true;
    28.     }
    29. };

    源码分析

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

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

    复杂度分析

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

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

    1. class Solution:
    2.     """
    3.     @param s: The first string
    5.     """
    6.     def anagram(self, s, t):
    7.         return sorted(s) == sorted(t)

    C++

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

    复杂度分析

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