알고리즘/자료구조

[LeetCode] 242. Valid Anagram - Java

2023. 8. 31. 22:25
목차
  1. 문제
  2. 내 풀이
  3. HashMap 사용
  4. 다른 사람의 풀이
 

Valid Anagram - LeetCode

Can you solve this real interview question? Valid Anagram - Given two strings s and t, return true if t is an anagram of s, and false otherwise. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using

leetcode.com

 

문제

더보기

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

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

 

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 * 104
  • s and t consist of lowercase English letters.

 

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

 

두 개의 문자열 s와 t가 주어졌을 때, s의 문자들을 재배열하여 t를 생성할 수 있는지 여부를 판별하는 문제이다.

 


 

내 풀이

HashMap 사용

class Solution {
    public boolean isAnagram(String s, String t) {

        Map<Character, Integer> map = new HashMap<>();

        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        for(int i=0; i<t.length(); i++){
            char c = t.charAt(i);

            if(map.containsKey(c)){
                if(map.get(c) == 1){
                    map.remove(c);
                }else{
                    map.put(c, map.get(c) -1);
                }
            }else{
                return false;
            }

        }

        if(map.size() > 0) return false;

        return true;
    }
}

 

  1. 해시 맵 map은 문자를 키로, 해당 문자의 빈도를 값으로 가진다.
  2. 문자열 s를 순회하며
    • 현재 문자 c의 빈도를 map에 업데이트한다.
    • 이미 map에 c가 있다면, 해당 문자의 빈도에 1을 더하고, 없다면 새로운 키로 추가하여 빈도를 1로 설정한다.
  3. 문자열 t를 순회하며
    • 현재 문자 c가 map에 있는지 확인한다
    • 있는 경우, 문자의 빈도가 1이라면 맵에서 해당 문자를 제거하고, 아니라면 빈도를 1 감소시킨다.
    • 없는 경우, 애너그램이 불가능하므로 false를 반환한다.
  4. map 에 문자가 남아있는 경우도 애너그램이 불가능한 경우이므로 false를 반환한다.
  5. 모든 로직을 통과하면 true를 반환한다.

 

  • 시간복잡도 : O(m + n) = O(n) - 문자열 순회
  • 공간복잡도 : O(n) - 해시 맵의 크기에 비례

 


 

다른 사람의 풀이

class Solution {
    public boolean isAnagram(String s, String t) {

        Map<Character, Integer> map = new HashMap<>();

         for (char x : s.toCharArray()) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }

        for (char x : t.toCharArray()) {
            map.put(x, map.getOrDefault(x, 0) - 1);
        }

        for(int count : map.values()){
            if(count != 0) return false;
        }

        return true;

    }
}

비슷한 로직이지만 훨씬 깔끔하다.

두 문자열을 모두 순회하며 빈도 차이를 맵에 저장하고 그 차이가 모두 0인지 확인하는 로직이다.

후… 처음부터 이렇게 깔끔하게 짜는 사람이 되도록 하자.

 

 

저작자표시 (새창열림)

'알고리즘 > 자료구조' 카테고리의 다른 글

[LeetCode] 230. Kth Smallest Element in a BST - Java  (0) 2023.09.08
[LeetCode] 530. Minimum Absolute Difference in BST - Java  (0) 2023.09.08
[LeetCode] 383. Ransom Note - Java  (0) 2023.08.31
[LeetCode] 219. Contains Duplicate II - Java  (0) 2023.08.31
[LeetCode] 1. Two Sum - Java  (0) 2023.08.31
  1. 문제
  2. 내 풀이
  3. HashMap 사용
  4. 다른 사람의 풀이
'알고리즘/자료구조' 카테고리의 다른 글
  • [LeetCode] 230. Kth Smallest Element in a BST - Java
  • [LeetCode] 530. Minimum Absolute Difference in BST - Java
  • [LeetCode] 383. Ransom Note - Java
  • [LeetCode] 219. Contains Duplicate II - Java
jny0
jny0
성장일기
jny0
J N Y 0
jny0
  • 분류 전체보기 (192)
    • 트러블슈팅 (6)
    • Java (22)
    • HTML, CSS , JavaScript (7)
    • MySQL, DBMS (9)
    • GIT (6)
    • 객체지향의 사실과 오해 (3)
    • 자바 ORM 표준 JPA 프로그래밍 (13)
    • 알고리즘 (114)
      • 자료구조 (59)
      • 수학 (11)
      • 정렬 (2)
      • 그리디 (3)
      • DP (4)
      • 그래프 (3)
      • 탐색 (9)
      • 재귀 (2)
      • 문자열 (9)
      • 기타 (12)
    • CS (10)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 글쓰기
  • 관리

공지사항

인기 글

태그

  • 투포인터
  • method
  • DP
  • 누적합
  • MySQL
  • codeup
  • 그리디
  • 백준
  • git
  • JS
  • BFS
  • 스택
  • JPA
  • 자료구조
  • 프로그래머스
  • 알고리즘
  • 구현
  • db
  • 영상후기
  • Java

최근 댓글

최근 글

hELLO · Designed By 정상우.
jny0
[LeetCode] 242. Valid Anagram - Java
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.