Anagrams--LeetCode

ゝ一纸荒年。 2022-08-05 14:16 125阅读 0赞

# 题目： #

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

# 思路： #

判断两个字符串是否为anagram的方法可以有：

1）将每个字符串的所有字符按字典序排列，比较是否相同。

2）用Hash表表示每个字符串的每个字符的出现次数。

3）用26个素数表示26个字符，字符串表示为所有字符数组对应的素数乘积。

从数据结构的角度考虑，可以使用hashmap(),排序等，这里说一个具体的做法，我们知道有26个字母，为每一个字符串都有一个bitmap，表示这个字符串出现了什么字符以及字符出现的次数，然后将bitmap进行排序，bitmap相同的就是可以组成anagrams对的情况，这里的bitmap使用string，但是为了记住bitmap对应的某一个字符串，我使用了pair，pair<string,int>，对每一个字符串建立对应的pair，将pair依据第一个字段排序，然后输出。

int myfunc(const pair<string,int>& l,const pair<string,int>& r)
    {
    	return l.first > r.first;
    }
    void Anagrams(vector<string>& vec)
    {
    	vector<pair<string,int> > hash;
    	int i,j;
    	for(i=0;i<vec.size();i++)
    	{
    		string tmp(26,'0');
    		for(j=0;j<vec[i].length();j++)
    		{
    			tmp[vec[i][j]-'a']++;
    		}
    		pair<string,int> index(tmp,i);
    		hash.push_back(index);
    	}
    	sort(hash.begin(),hash.end(),myfunc);
    
    	for(i=0;i<hash.size();)
    	{
    		for(j=i+1;j<hash.size();j++)
    		{
    			if(hash[j].first == hash[i].first)
    				cout<<vec[hash[j-1].second]<<endl;
    			else
    				break;
    		}
    		if(j-i>1)
    		{
    			cout<<vec[hash[j-1].second]<<endl;
    			cout<<"==========="<<endl;
    		}
    		i =j;
    	}
    }

上述这种思路感觉有点乱，从上述的解释大概了解到，先讲字符串进行转化，比如使用素数转化，那么可以使用map<int,int>来表示，第一个int是讲每个字符串转换为素数之后的值，第二个是这个素数值的个数，如果发现这个数已经存在，那么就是目标值。下面讲述的这种方法也是这个思想。  
再说一种：

这个题简单的版本是判断两个单词是不是anagram，一般来说有两种方法。第一种方法是用hashmap，key是字符，value是出现的次数，如果两个单词构成的hashmap相同，那么就是anagram。实现起来就是用一个构建hashmap，然后另一个在前面的hashmap中逐个去除，最后如果hashmap为空，即返回true。这个方法时间复杂度是O(m+n)，m，n分别是两个单词的长度。而空间复杂度是O(字符集的大小)。第二种方法是将两个单词排序，如果排序之后结果相同，就说明两个单词是anagram。这种方法的时间复杂度取决于排序算法，一般排序算法是O(nlogn)，如果字符集够小，也可以用线性的排序算法。不过总体来说，如果是判断两个单词的，第一种方法要直接简单一些。  
接下来我们看看这道题，是在很多字符串里面按照anagram分类，如果用hashmap的方法，然后两两匹配，在分组会比较麻烦。而如果用排序的方法则有一个很大的优势，就是排序后的字符串可以作为一个key，也就是某一个class的id，如此只要对每一个字符串排序，然后建立一个hashmap，key是排序后的串，而value是所有属于这个key类的字符串，这样就可以比较简单的进行分类。假设我们有n个字符串，字符串最大长度是k，那么该算法的时间复杂度是O(nklogk)，其中O(klogk)是对每一个字符串排序（如果用线性算法也可以提高）。空间复杂度则是O(nk)，即hashmap的大小。实现代码如下：

public ArrayList<String> anagrams(String[] strs) {  
            ArrayList<String> res = new ArrayList<String>();  
            if(strs == null || strs.length == 0)  
                return res;  
            HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();  
            for(int i=0;i<strs.length;i++)  
            {  
                char[] charArr = strs[i].toCharArray();  
                Arrays.sort(charArr);  
                String str = new String(charArr);  
                if(map.containsKey(str))  
                {  
                    map.get(str).add(strs[i]);  
                }  
                else  
                {  
                    ArrayList<String> list = new ArrayList<String>();  
                    list.add(strs[i]);  
                    map.put(str,list);  
                }  
            }  
            Iterator iter = map.values().iterator();  
            while(iter.hasNext())  
            {  
                ArrayList<String> item = (ArrayList<String>)iter.next();  
                if(item.size()>1)  
                    res.addAll(item);  
            }  
            return res;  
        }

实现起来还是比较简单的，这道题考察排序，hashmap，字符串处理。

Anagrams--LeetCode

发表评论取消回复

还没有评论，来说两句吧...

相关阅读