LeetCode-Anagrams

Love The Way You Lie 2022-08-07 05:42 120阅读 0赞

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

Note: All inputs will be in lower-case.

首先理解一下题，什么是anagrams，就是，在String1里出现过的字符在String2里也都出现过，并且个数是一样的。

比如 “dog” , “gdo”是，更显示的是，“dog”的全排列都是anagrams。并且此题并不是真正的groups，比如输入\{“dog”，“god”，“dgo”\}，应该的输出也是\{“dog”，“god”，“dgo”\}。理解的差不多就可以了。

解题思路：因为涉及到快速查找，很显然要用哈希。关键问题就是怎么用哈希，快速定位。

我的哈希是：

Map<String,List<String>> resMap = new HashMap<String,List<String>>();

先讲解key的实现，根据题意怎么才能把是一个anagram的映射到同一个key上，这是本题的解题关键。很显然，如果把每个字符串排序当做key，value是排序前的，也是可以的。

我的实现是这样的，从a到z计算每个 字符出现的次数，没有出现的就不用管了。具体代码如下：

private String getKey(String s) {
        	StringBuilder sb = new StringBuilder();
        	char[] chars = s.toCharArray();
        	int[] table = new int[26];
        	for (int i = 0; i < chars.length; i++) {
        		table[chars[i]-'a']++;
        	}
        	for (int i = 0; i < 26; i++) {
        		if (table[i] > 0) {
        			sb.append((char)(i+'a')).append(table[i]);
        		}
        	}
        	return sb.toString();
        }

这样应该比排序的方法要快吧！！！所以，本题的解法就呈现出来了，如下：

public List<String> anagrams(String[] strs) {
        	List<String> res = new ArrayList<String>();
            if (strs.length==0 || strs.length==1) return res;
    
            Map<String,List<String>> resMap = new HashMap<String,List<String>>();
            List<String> keyList = new ArrayList<String>(); 
    
            for (int i = 0; i < strs.length; i++){
                String key = getKey(strs[i]);
                if (resMap.containsKey(key)) {
                    resMap.get(key).add(strs[i]);
                } else {
                    List<String> list = new ArrayList<String>();
                    list.add(strs[i]);
                    resMap.put(key,list);
                    keyList.add(key);
                }
            }
            for (int i = 0; i < keyList.size();i++){
                List<String> list = resMap.get(keyList.get(i));
                if (list.size() > 1) {
                	res.addAll(list);
                }
            }
            return res;
        }

LeetCode-Anagrams

发表评论取消回复

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

相关阅读