LintCode 158: Anagram

题目描述

写出一个函数anagram(s, t)判断两个字符串是否可以通过改变字母的顺序变成一样的字符串。

样例

给出s = "abcd"，t="dcab"，返回true.

给出s = "ab", t = "ab", 返回true.

给出s = "ab", t = "ac", 返回false.

Mon Mar 6 2017

思路

这道题很容易想到先将字符串排序，然后比较两个字符串是否相等，这种方法的时间复杂度为\(O(nlogn)\)。

但是题目中有更高的要求，要求时间复杂度为\(O(n)\)，空间复杂度为\(O(1)\)，所以需要借助哈希表统计各字符出现的次数。

分别统计两个字符串中各字符串出现的次数，若在字符串s出现过，则+1，若在字符串t出现过，则-1，最后检查次数是否全为0即可。

代码

// 两个字符串是变位词

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.size() != t.size()) return false;

        int count[256] = {0};

        for (int i = 0; i < s.size(); ++i)

        {

            ++count[s[i]];

            --count[t[i]];

        }

        for (int i = 0; i < 256; ++i)

            if (count[i] < 0)

                return false;

        return true;

    }

};