(LeetCode) 242. Valid Anagram

242. Valid Anagram

• Explore : Interview > Top Interveiw Questions > Easy Collection
• 분류 : String
• 난이도 : Easy

Problem

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Example 1

Input: s = "anagram", t = "nagaram"
Output: true

Example 2

Input: s = "rat", t = "car"
Output: false

Constraints

• 1 <= s.length, t.length <= 5 * 10^4
• s and t consist of lowercase English letters.

Solution (Raw)

Exapnder

class Solution {
    fun isAnagram(s: String, t: String): Boolean {
        if (s.length != t.length) {
            return false
        }
        var sMap = HashMap<Char, Int>()
        s.forEach {
            if (sMap.containsKey(it)) {
                var value = sMap[it]!!
                sMap[it] = value + 1
            } else {
                sMap[it] = 1
            }
        }

        var tMap = HashMap<Char, Int>()
        t.forEach {
            if (tMap.containsKey(it)) {
                var value = tMap[it]!!
                tMap[it] = value + 1
            } else {
                tMap[it] = 1
            }
        }

        sMap.forEach {
            var key = it.key
            var value = it.value
            if (!tMap.containsKey(key) || tMap[key] != value) {
                return false
            }
        }
        return true
    }
}

Solution (Short)

Exapnder

class Solution {
    fun isAnagram(s: String, t: String): Boolean {
        if (s.length != t.length) {
            return false
        }
        var input = IntArray(26) { 0 }
        s.forEach {
            input[it.toIndex()]++
        }
        t.forEach {
            if (--input[it.toIndex()] < 0) {
                return false
            }
        }
        return true
    }

    fun Char.toIndex(): Int = this - 'a'
}

Point of Thinking

• 애너그램의 정의
  • 글자수의 길이가 동일해야 한다.
  • 재배열시 사용한 문자 수가 동일해야한다.
• Solution (Raw) 의 방법
  • 문자열의 길이가 다르면 바로 false
  • 주어진 문자열 s와 t를 각각의 문자를 key로 하는 map으로 바꾸고, 등장한 수만큼 value로 저장한다.
  • 두 개의 map을 순회하며, key가 없다면 다른 문자가 등장한 것이므로 false, value가 다르다면 사용 횟수가 다르므로 false
  • 그 외의 경우는 true
• Solution (Short) 의 방법
  • Raw를 토대로 한 번 줄여보았다.
  • map 대신 array를 쓰고, 영어 소문자인 26개의 크기를 지정한다.
  • s를 순회하며 소문자에 해당하는 index 값을 증가시킨다.
  • t를 순회하며 소문자에 해당하는 idnex 값을 감소시켰을 때 0미만이면 false
  • 그 외의 경우는 true