Beat 96% without sorting, but easy to break...


  • 0
    V

    public class Solution {

    public List<List<String>> groupAnagrams(String[] strs) {
        int[] primeArr = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
                73, 79, 83, 89, 97, 101};
    
        List<List<String>> result = new ArrayList<>();
        HashMap<Integer, List<String>> hashMap = new HashMap<>();
        for (String s : strs) {
            int index = 1;
            for (char c : s.toCharArray()) {
                index *= primeArr[c - 'a'];
            }
            if (!hashMap.containsKey(index)) {
    
                hashMap.put(index, new ArrayList<>());
    
            }
            hashMap.get(index).add(s);
        }
    
        for (List<String> list : hashMap.values()) {
            result.add(list);
        }
        return result;
        
    }
    

    }


  • 0

    Easy to break, fails for example this input:

    ["aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaafoobar"]


  • 0
    V

    Thank you. You are right.It's easy to break. I knew this function has its limitation,but it works for this problem.The problem needs more test cases. Thank you so much


  • 0

    You could btw make it stronger and harder to break by replacing the prime 2 with the prime 103. Problem was that due to overflow, you're calculating modulo a power of 2, so using 2 as factor gave me the easy breaking example.

    I did something similar now for the other anagram problem, using a formula for primes because I find that neater.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.