乱序字符串算法

た入场券 2022-09-24 12:23 187阅读 0赞

## 乱序字符串 ##

**蛮力法**

题目链接：[lintcode乱序字符串题目链接][lintcode]

> 思路等会睡醒之后写吧

#include "string"
    #include "algorithm"
    #include "stdio.h"
    #include "iostream"
    #include "vector"
    using namespace std;
    bool Isanagram(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;
    }
    vector<string> anagrams(vector<string> &strs) {
        int mark[10001]={
       0};
        int i,j;
        vector<string> ans;
        for( i=0;i<strs.size();i++)
        {
            if(mark[i])
                continue;
            else
                ans.push_back(strs[i]);
            int flag=0;
            for(j=i+1;j<strs.size();j++)
            {
                if(mark[j]) continue;
                if(Isanagram(strs[i],strs[j]))
                {
                    mark[j]=1;
                    flag=1;
                    ans.push_back(strs[j]);
                }
            }
            if(!flag) ans.pop_back();
        }
        return ans;
    }  
    int main()
    {
        int N,i;
        cin>>N; //输入字符串数组长度
        vector<string> str(N);
        for(int i=0;i<N;i++)
             cin>>str[i];
        str=anagrams(str);
        for(i=0;i<str.size();i++)
            cout<<str[i]<<" ";
        return 0;
    }

用哈希法配合排序解决

> 等我睡醒

#include "string"
    #include "algorithm"
    #include "stdio.h"
    #include "iostream"
    #include "vector"
    #include "map"
    using namespace std;
    
    vector<string> anagrams(vector<string> &strs) {
        int i;
        vector<string> ans;
        map<string,int> my_map;
        for(i=0;i<strs.size();i++)
        {
            string str=strs[i];
            sort(str.begin(),str.end());
            my_map[str]++;
        }
        for(i=0;i<strs.size();i++)
        {
            string str=strs[i];
            sort(str.begin(),str.end());
            if(my_map[str]>1)
                ans.push_back(strs[i]);
        }
        return ans;
    }  
    int main()
    {
        int N,i;
        cin>>N;
        vector<string> str(N);
        for(int i=0;i<N;i++)
             cin>>str[i];
        str=anagrams(str);
        for(i=0;i<str.size();i++)
            cout<<str[i]<<" ";
        return 0;
    }

[leetcode练习链接][leetcode]

这里需要排序输出，稍微有点复杂。

#include "string"
    #include "algorithm"
    #include "stdio.h"
    #include "iostream"
    #include "vector"
    #include "map"
    using namespace std;
    typedef pair<string,int> PAIR;
    static int cmp(const PAIR &x,const PAIR &y)
    {
        return x.second>y.second;
    }
    vector<vector<string>> groupAnagrams(vector<string> &strs) {
        int i;
        map<string,vector<string>> temp_map;
        map<string,int> index;
        vector<vector<string>> ans;
        for(i=0;i<strs.size();i++)
        {
            string str=strs[i];
            sort(str.begin(),str.end());
            temp_map[str].push_back(strs[i]);
            index[str]++;
        }
        vector<PAIR> map_pair;
        map<string,int>::iterator it;
        vector<PAIR>::iterator lt;
        vector<string>::iterator lj;
        for(it=index.begin();it!=index.end();it++)
            map_pair.push_back(make_pair(it->first,it->second));
        sort(map_pair.begin(),map_pair.end(),cmp);
    
        for(lt=map_pair.begin();lt!=map_pair.end();lt++)
        {
            vector<string> v;
            sort(temp_map[lt->first].begin(),temp_map[lt->first].end());
            for(lj=temp_map[lt->first].begin();lj!=temp_map[lt->first].end();lj++)
                v.push_back(*lj); 
            ans.push_back(v);
            v.clear();
        }
        return ans;
    }  
    int main()
    {
        int N,i,j;
        vector<vector<string>> ans;
        cin>>N;  //输入的字符串数
        vector<string> str(N);
        for(int i=0;i<N;i++)
             cin>>str[i];
        ans=groupAnagrams(str);
        for(i=0;i<ans.size();i++)
        {
            for(j=0;j<ans[i].size();j++)
                cout<<ans[i][j]<<" ";
            cout<<endl;
        }
    
        return 0;
    }

[lintcode]: http://www.lintcode.com/zh-cn/problem/anagrams/
[leetcode]: https://leetcode.com/problems/anagrams/