Anagram -- Leetcode

1. Valid Anagram:

Question:
https://leetcode.com/problems/valid-anagram/

Solution:

    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
       
        int[] charArr = new int[26];
        char[] chars = s.toCharArray();
        char[] chart = t.toCharArray();
        for(int i=0; i<s.length(); ++i){
            charArr[chars[i]-'a']++;
        }
        for(int i=0; i<t.length(); ++i){
            if(--charArr[chart[i]-'a'] < 0){
                return false;
            }
        }
        return true;
    }


2. Group Anagram

Question:
https://leetcode.com/problems/anagrams/

Solution:
Method 1:
key = String (sorted)
value = List<String>
Group : HashMap< String, List<String> >

Time: O(n * mlog m)

    public List<List<String>> groupAnagrams(String[] strs) {
        List<String> subres = new ArrayList<String>();
        List<List<String>> res = new ArrayList<List<String>>();
        Map<String, List<String>> hmap = new HashMap<String, List<String>>();
       
        //Time : n * logn
        Arrays.sort(strs);
        //Time : n * mlogm, Space : hmap : O(n)
        for(String s : strs){
            //sort s to get key, nlogn
            char[] charArr = s.toCharArray();
            Arrays.sort(charArr);
            String sortedStr = String.valueOf(charArr);
           
            if(!hmap.containsKey(sortedStr)){
                hmap.put(sortedStr, new ArrayList<String>());
            }
            hmap.get(sortedStr).add(s);
        }
       
        res.addAll(hmap.values());
        return res;
    }



Method 2:
key = HashMap<Character, Integer>
value = List<String>
Group : HashMap< HashMap<Character, Integer>, List<String> >

Time: O(n * (m + 26))

public List<List<String>> groupAnagrams(String[] strs) {
        List<String> subres = new ArrayList<String>();
        List<List<String>> res = new ArrayList<List<String>>();
        Map<String, List<String>> hmap = new HashMap<String, List<String>>();
       
        Arrays.sort(strs);
        //O(n)
        for(String s : strs){
            int[] charArr = new int[26];
            char[] chars = s.toCharArray();
            //Time : O(m + 26), Space : O(26) + O(n)
            for(int i=0; i<s.length(); ++i){
                charArr[chars[i]-'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<26;++i){
               sb.append("" + i + charArr[i]);
            }
            String setStr = sb.toString();
           
            if(!hmap.containsKey(setStr)){
                hmap.put(setStr, new ArrayList<String>());
            }
            hmap.get(setStr).add(s);
        }
       
        res.addAll(hmap.values());
        return res;
    }