[Dart] 242. Valid Anagram

1. 문제

https://leetcode.com/problems/valid-anagram/?envType=study-plan-v2&envId=top-interview-150

 

 

 

 

2. 요구사항

1) 두 개의 문자열 s와 t가 있다.

2) t가 s의 애너그램이면 true를 반환하고, 아니면 false를 반환한다.

3) 애너그램은 두 문자열이 같은 문자를 같은 개수만큼 가지고 있지만, 순서는 다른 경우를 말한다.

 

 

 

 

3. 핵심 아이디어

1) List에 알파벳이 나온 횟수 저장

 

알파벳 소문자 a부터 z의 각 문자의 등장 횟수를 저장할 List<int>를 생성한다.

 

s문자열을 순회하며 각 문자의 개수를 증가한다.

 

t문자열도 순회하며 각 문자의 개수를 감소한다.

 

리스트 배열에 문자가 남아있는지, 남아있지 않은지로 애너그램을 판별한다.

 

 

2) 코드

class Solution {
  bool isAnagram(String s, String t) {
    // 길이가 다르면 절대 애너그램이 될 수 없음
    if (s.length != t.length) return false;

    // 알파벳 소문자 a~z 개수를 담을 리스트 (총 26개)
    List<int> count = List<int>.filled(26, 0);

    // 'a'의 아스키 코드값을 기준점으로 삼음
    final baseUnit = "a".codeUnitAt(0);

    // 첫 번째 문자열 s의 각 문자를 count 배열에 기록
    for (var i = 0; i < s.length; i++) {
      final index = s.codeUnitAt(i) - baseUnit;
      count[index] += 1;  // 해당 알파벳의 개수 증가
    }

    // 두 번째 문자열 t를 돌면서 s에서 뺀 알파벳인지 확인
    for (var j = 0; j < t.length; j++) {
      final index = t.codeUnitAt(j) - baseUnit;

      // 문자가 더 이상 남아있지 않으면 애너그램 아님
      if (count[index] - 1 < 0) {
        return false;
      }

      // 해당 알파벳 하나 사용 (개수 줄임)
      count[index] -= 1;
    }

    // 위 과정 통과하면 애너그램 맞음
    return true;
  }
}