(LeetCode) Valid Anagram

Valid Anagram

  • 분류 : String
  • 난이도 : Easy

Problem

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

Example 1

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

Example 2

1
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
    • 주어진 문자열 st를 각각의 문자를 key로 하는 map으로 바꾸고, 등장한 수만큼 value로 저장한다.
    • 두 개의 map을 순회하며, key가 없다면 다른 문자가 등장한 것이므로 false, value가 다르다면 사용 횟수가 다르므로 false
    • 그 외의 경우는 true
  • Solution (Short) 의 방법
    • Raw를 토대로 한 번 줄여보았다.
    • map 대신 array를 쓰고, 영어 소문자인 26개의 크기를 지정한다.
    • s를 순회하며 소문자에 해당하는 index 값을 증가시킨다.
    • t를 순회하며 소문자에 해당하는 idnex 값을 감소시켰을 때 0미만이면 false
    • 그 외의 경우는 true