[CareerCu] Arrays and Strings—Q1.4

題目：

Write a method to decide if two strings are anagrams or not.

翻譯：

寫一個方法來判斷兩個字符串是否互為變位詞。

注：如果構成兩個字符串的字符完全相同，而對應字符所處的位置不同，則稱這兩個字符串互為變位詞。如：abbfcad和facbdab互為變位詞。

思路：

很多人應該一下子就能想到對兩個字符串按照在字典中出現的先後順序進行排序，而後再對排序後的兩個字符串逐個比較，如果兩個字符串相等，則二者互為變位詞，否則，不互為變位詞。

事實上，和Q1.1的思路一樣，我們同樣沒有必要對字符串進行排序，我們同樣可以利用哈希的思想（到現在為止，四個題目中已經有三個用到了哈希的思想），開辟一個大小為26（假設字符串中的字符為26個小寫字母）的int數組，初始值均為0，先對第一個字符串進行映射，每個字符在該字符串中出現一次，數組的對應位置的值就加1，而後再對第二個字符串進行映射，每個字符在該字符串中出現一次，數組中對應位置的值就減1，如果最後該數組的所有元素值均為0，則說明這兩個字符串互為變位詞。該方法的時間復雜度為O（n）。

實現代碼:

/****************************
題目描述：
判斷兩個字符串是否互為變位詞
Date:2014-03-17
****************************/
#define MAX 26
#include
#include
using namespace std;

bool anagram(string s1,string s2)
{
	int len1 = s1.length();
	int len2 = s2.length();
	if(len1 != len2)
		return false;

	int i;
	int A[MAX];
	memset(A,0,sizeof(A));
	for(i=0;i 0)
			return false;
	return true;
}

int main()
{
	string s1 = abbfcad;
	string s2 = facbdab;
	if(anagram(s1,s2))
		cout<     測試結果：