Skip to content

LeetCode - 1347. Minimum Number of Steps to Make Two Strings Anagram

개요

글자 개수가 같은 두 문자열 s와 t가 주어진다. t의 문자들을 바꿔 s의 Anagram으로 만들어야 한다.

  • Anagram: 두 문자열이 주어졌을 때, 구성하는 문자는 같으나 위치만 다른 두 문자열을 Anagram관계에 있다고 한다.

이 때, 문자열 t가 s의 Anagram이 되기 위한 바꿔야 할 최소 문자의 개수를 구하라.

이해한 부분

s 가 Anagram 대상이고, t를 최소한으로 바꾸어 s의 Anagram으로 만들어야 한다.

모호한 부분

Anagram이 순서 상관 있을까? - 순서 상관 없이 character 개수와 종류만 맞으면 되었다.

해결 전략

1. hash Table 비교

s와 t를 각각 구성하는 문자와 문자 개수를 저장하는 hash table를 생성한다.

leetcode = 8자
        l = 1, e = 3, t = 1, c = 1, o = 1, d = 1
practice = 8 자
        p = 1, r = 1, a = 1, t = 1, i = 1, c = 2, e = 1

l = 1, l = 0, abs(1 - 0), 8 - 1 => 7
e = 3, e = 1, abs(3 - 1), 7 - 2 => 5
t = 1, t = 1, abs(1 - 1), 5 - 0 => 7
c = 1, c = 2, abs(1 - 2), 5 - 1 => 5 (X) 0 이하면 세지말아야 함
o = 1, o = 0, abs(1 - 0), 5 - 0 => 5
d = 1, d = 0, abs(1 - 0), 5 - 0 => 5

즉, 바꿔야 할 문자의 개수는 5개가 나온다.

회고

이번 문제는 정보가 많이 주어졌다.

두 문자열 s와 t의 개수가 같다는 점.

목표도 s를 대상으로 t를 바꿔 만들 수 있는 Anagram으로 명확하였다.

또한, s 혹은 t로 바꿔 만들 수 있는 Anagram의 최소 문자 개수를 구한다고 해도 위의 문제를 응용하여 해결할 수 있을 것 같다. 구조는 아래와 같다.

def solution(s, t):
    return min(calcNumOfAnagram(s,t),calcNumOfAnagram(t,s))


#coding-interview #hashmap

Comments