关于字符串的算法

Bertha 。 2022-09-24 12:20 85阅读 0赞

## 两个串是相同字母异序词 ##

Two Strings Are Anagrams  
lintcode: (158)[Two Strings Are Anagrams ][Two Strings Are Anagrams]

> Clarification What is Anagram?  
> \- Two strings are anagram if they can be the same after change the order of characters. Example
> 
> Given s = “abcd”, t = “dcab”, return true. Given s = “ab”, t = “ab”,  
> return true. Given s = “ab”, t = “ac”, return false

解题思路；

> 第一种解法：  
> 这里可以采用哈希的方法，用map数组来标记是否字符出现过。并用一个二维数组记录下出现的次数。因为一个字符可能出现好多次，之后进行比较即可。map键值的求解方法为：target\[i\]-NULL。因为NULL的ASSIC值为0所以这里减去的话就会避免出现负数的可能性。

#include "string"
    #include "stdio.h"
    #include "iostream"
    using namespace std;
    bool anagram(string source, string target) {
            int i,count=0;
            int map[1001][2];
            memset(map,0,sizeof(map));
            if(source.length()!=target.length())
                return false;
            for(i=0;i<target.length();i++)
            {
                map[target[i]-NULL][0]=1;
                map[target[i]-NULL][1]++;
    
            }
            for(i=0;i<source.length();i++)
            {
                if(map[source[i]-NULL][0]==1 && map[source[i]-NULL][1]>0)
                {
                    count++;
                    map[source[i]-NULL][1]--;
                }
            }
            if(count==source.length())
                return true;
            return false;
    }
    int main()
    {
        string source,target;
        getline(cin,source);
        getline(cin,target);
        cout<<anagram(source,target)<<endl;//相同的字母或者异序词
        return 0;
    }

> 上面的算法很容易想到所以还可以进行优化：  
> 我们可以设置一个数组letterCount,用来统计两个字符串中各个字符各自出现的次数，如果源字符串中出现一次，如果两个字符串是相同异序川，那么对应的目标字符串中也应该出现一次。由此我们可以知道  
> Count( source \[ i \] )==Count( target \[ i \] ).

#include "string"
    #include "stdio.h"
    #include "iostream"
    using namespace std;
    bool anagram(string source, string target) {
            int i,count=0;
            int letterCount[256]={
       0};
            if(source.size()!=target.size())
                return false;
            for(i=0;i<source.length();i++)
            {
                 letterCount[source[i]]++;
                 letterCount[target[i]]--;
            }
            for(i=0;i<source.length();i++)
            {
                 if(letterCount[target[i]]!=0)//判断为0即可
                     return false;
            }
            return true;
    }
    int main()
    {
        string source,target;
        getline(cin,source);
        getline(cin,target);
        cout<<anagram(source,target)<<endl;//相同的字母或者异序词
        return 0;
    }

> 第二种解法：  
> 这里可以直接对两个字符串进行排序，如果排序后二者完全相同，那么就是相同异序串。

#include "string"
    #include "stdio.h"
    #include "iostream"
    #include "algorithm"
    using namespace std;
    bool anagram(string source, string target) {
            if(source.size()!=target.size())
                return false;
            sort(source.begin(),source.end());
            sort(target.begin(),target.end());
            if(source==target)
                return true;
            return false;
    }
    int main()
    {
        string source,target;
        getline(cin,source);
        getline(cin,target);
        cout<<anagram(source,target)<<endl;//相同的字母或者异序词
        return 0;
    }

[Two Strings Are Anagrams]: http://www.lintcode.com/en/problem/two-strings-are-anagrams/