Anagram related

Leave a comment

November 5, 2016 by oneOokay

Valid Anagram:

  • 如果input string都是a-z的话最简单的方法是:一个char[26] array,对应的每个char出现的次数为第[char – ‘a’]个元素的值,loop一遍放入string1,loop第二遍string2进行减法,loop第三遍进行判断是否每个元素都为0.
  • 如果input string包含unicode characters,用HashMap<Character, Integer>() 外加一个count为string1的长度。 loop string1一遍放入,loop string2,如果char不存在map中,return false;当map.get(c) > 0 的时候,把它的值-1并且count -1.最后return count == 0.

Group Anagram:

第一个想到的就是直接用Arrays.sort()来做,但是觉得不够高效也想不出其他的好的。但是看答案大家都这么做。

容易想到的是用HashMap<String, List>, 最终在把hashmap的values存到ans list里面.

for (String s : map.keySet()){
ans.add(map.get(s));
}

更好的就是直接hashmap里面存ans list的index, 直接把string存到ans list里面而不是在hashmap里.

arraylist.get(index)

public List groupAnagrams(String[] strs) {
        List ans = new ArrayList<>();
        if (strs == null || strs.length == 0){
            return ans;
        }
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for (int i = 0; i < strs.length; i ++){
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            String newStr = String.valueOf(chars);
            if (!map.containsKey(newStr)){
                map.put(newStr, ans.size());
                List l = new ArrayList();
                ans.add(l);
            }
            int index = map.get(newStr);
            ans.get(index).add(strs[i]); 
        }
        return ans;
    }

另外有一个without sort()的方法:是个很好的思想,但是容易overflow

用一系列的prime number来代表a-z,对于每个string,把他的每个char代表的prime number相乘得到一个值为hashmap的key,之后的所有string只要乘积相等,则为anagram。

Find All Anagrams in a String: TODO

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: