Kotlin set Array as key for a HashMap

Question

I'm doing a bit of Leetcode, and I'm facing this issue: Group Anagrams, I have a Python background and I can do the following:

res = defaultdic(list)

count = [0] * 26

res[tuple(count)].append(s)

as we can see we can set the tupled array as the key for the dictionary, I want to do the same thing in Kotlin, however, when creating this in Kotlin, I get a different object every time when adding this logic in a for loop.

fun groupAnagrams(strs: Array<String>): List<List<String>> {
    val hashMap = hashMapOf<IntArray, ArrayList<String>>()

    for (word in strs) {
        val array = IntArray(26) { 0 }

        for (char in word) {
            val charInt = char - 'a'

            array[charInt] += 1
        }

        if (hashMap.containsKey(array)) {
            hashMap[array]!!.add(word)
        } else {
            hashMap[array] = ArrayList<String>().apply { add(word) }
        }
    }

    return hashMap.values.toList()
}

Is this something can be done in Kotlin?

Alternatively to the provided solution one could also use the contentHashCode of an array like this: hashMap[array.contentHashCode()] This eliminated the need to use a List. — MEX
– MEX, Commented Feb 15, 2023 at 22:35

Arpit Shukla · Accepted Answer · 2021-11-03 06:03:03Z

7

Equality for IntArray is checked based on its reference. You can use a List here in place of IntArray. Two Lists are equal if they contain the same elements.

Modified code will be like this:

fun groupAnagrams(strs: Array<String>): List<List<String>> {
    val hashMap = hashMapOf<List<Int>, ArrayList<String>>()

    for (word in strs) {
        val array = List(26) { 0 }.toMutableList()

        for (char in word) {
            val charInt = char - 'a'
            array[charInt] += 1
        }

        if (hashMap.containsKey(array)) {
            hashMap[array]!!.add(word)
        } else {
            hashMap[array] = ArrayList<String>().apply { add(word) }
        }
    }

    return hashMap.values.toList()
}

answered Nov 3, 2021 at 6:03

Arpit Shukla

10.6k2 gold badges23 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

gidds Over a year ago

May also be worth renaming array since it's no longer an array :-) And worth pointing out that if you use mutable objects as map keys, you must ensure that they can't change thereafter; if they do, then the map can behave inconsistently, being unable to find keys or even throwing exceptions.

Arpit Shukla Over a year ago

Are you referring to this code in your second point? I didn't get that. Where are mutable keys here?

gidds Over a year ago

My second was a general point that people should be aware of, not a problem with anything in your answer. (Feel free to add it to your answer if you want.)

David Soroko · Accepted Answer · 2021-11-03 20:47:01Z

0

Avoiding the problem you run into (equality of arrays) by using String keys:

fun groupAnagramsWithHashing(strs: Array<String>): List<List<String>> {
    val map = hashMapOf<String, MutableList<String>>()

    MessageDigest.getInstance("SHA-1").also { sha ->
        for (word in strs) {
            word.toByteArray().sorted().forEach { sha.update(it) }

            val key = sha.digest().joinToString()
            map.computeIfAbsent(key) { mutableListOf() }.add(word)
        }
    }
    return map.values.toList()
}

fun main() {
    val input = arrayOf("eat", "tea", "tan", "ate", "nat", "bat")
    groupAnagramsWithHashing(input).also { println(it) }
    // [[eat, tea, ate], [bat], [tan, nat]]
}

edited Nov 3, 2021 at 20:47

answered Nov 3, 2021 at 19:53

David Soroko

9,3743 gold badges44 silver badges59 bronze badges

Collectives™ on Stack Overflow

Kotlin set Array as key for a HashMap

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related