[LeetCode] Valid Anagram - 字符串排序比较系列

题目概述：

Given two strings s and t, write a function to determine if t is an anagram of s.
For example,
        s = "anagram", t = "nagaram", return true.
        s = "rat", t = "car", return false.
Note: You may assume the string contains only lowercase alphabets.

解题方法：
        该题意是比较两个字符串s和t，其中t是次序打乱的字符串，如果两个字符串相同则返回true，否则false。方法包括：(参考)
        方法一
        最简单的方法就是字符串s和t分别排序，在比较两个字符串是否相同。但是会报错TLE- Time Limit Exceeded
        同样采用选择排序每次比较最小字符，不同则跳出循环返回false也TLE。
bool isAnagram(char* s, char* t) {int ls,lt; //字符串长度int i,j;char ch;if(s==NULL&&t==NULL)return true;ls=strlen(s);lt=strlen(t);if(ls!=lt)return false;//方法一 排序后判断字符串是否相等for(i=0; i<ls; i++) {for(j=i+1; j<ls; j++) {if(s[i]>=s[j]) {ch=s[i];s[i]=s[j];s[j]=ch;}if(t[i]>=t[j]) {ch=t[i];t[i]=t[j];t[j]=ch;}}}if(strcmp(s,t)==0)return true;elsereturn false; }         方法二
        后来百度下发现如果采用Java代码，通过调用内部的sort排序则会AC，但个人不喜欢调用内部函数的方法。
public class Solution { public boolean isAnagram(String s, String t) { char[] sArr = s.toCharArray(); char[] tArr = t.toCharArray(); Arrays.sort(sArr); Arrays.sort(tArr); return String.valueOf(sArr).equals(String.valueOf(tArr)); } }         C++调用sort排序代码如下：
class Solution { public:bool isAnagram(string s, string t) {sort(s.begin(), s.end());sort(t.begin(), t.end());return s == t;} };         方法三
        计算字符串字母个数，比较值都相同则true，否则返回false。
        方法四 (强推)
        通过一个长度为26的整形数组，对应英文中的26个字母a-z。从前向后循环字符串s和t，s中出现某一字母则在该字母在数组中对应的位置上加1，t中出现则减1。如果在s和t中所有字符都循环完毕后，整型数组中的所有元素都为0，则可认为s可由易位构词生成t。 bool isAnagram(char* s, char* t) {int ls,lt; //字符串长度int i;int num[26]={0};if(s==NULL&&t==NULL)return true;ls=strlen(s);lt=strlen(t);if(ls!=lt)return false;//方法四 计算字母个数 s中出现+1,t中出现-1,整个数组26个数都为0时则表示相同for(i=0; i<ls; i++) {num[s[i]-'a']++;num[t[i]-'a']--;}for(i=0; i<26; i++) {if(num[i]!=0)return false;}return true; }         而且最后的时间结果也比较优秀： C++调用sort代码-76ms； Java调用sort代码-288ms；C语言计算字母个数-0ms。


(By:Eastmount 2015-9-14 清晨7点半     http://blog.csdn.net/eastmount/ )

总结

以上是生活随笔为你收集整理的[LeetCode] Valid Anagram - 字符串排序比较系列的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。