Tag Archives: 变位词

关于变位词

首先判断两个string是否互为变位词。

/*******************************************/
/*decide if two strings are anagrams or not*/
/*******************************************/
/*sort the string*/
bool anagram(string s,string t)
{
	sort(s.begin(),s.end());
	sort(t.begin(),t.end());
	return (s == t);
}

/*Check if the two strings have identical counts for each unique char*/
static bool anagram2(string s,string t)
{
	if(s.length()!=t.length())
		return false;
	int *letters=new int[256](); //()!初始化为0
	int num_unique_chars=0;
	int num_completed_t=0;

	const char *s_array=s.c_str();
	for(int i=0;i<strlen(s_array);++i)
	{
		if(letters[s_array[i]] == 0)
			++num_unique_chars;
		++letters[s_array[i]];
	}
	
	for(int i=0;i<t.length();++i)
	{
		int c=(int)t[i];
		if(letters[c]==0)
		{
			return false;//t中有非s中的新字符
		}
		--letters[c];
		if(letters[c]==0)
		{
			++num_completed_t;//比较完一个字符
			if(num_completed_t==num_unique_chars)
			{
				return i==t.length()-1;//比较完所有字符,t正好处理完
			}
		}
	}
	return false;
}

其次,再来看N多单词的。下次再来补充,今天累了……
参考夏同学的:http://blog.csdn.net/coder_xia/article/details/7550513