LeetCode :: Valid Anagram (Java)

😃 || 정리

Anagram이 뭔지 검색해보니 주어진 알파벳으로 해당 단어를 만들 수 있는지 가늠하는 것이라고 한다.
예를 들어 "papel" 주어지면 "apple"을 만들 수 있으므로 해당 문자는 true를 반환하게 된다. 
 그래서 이 문제를  풀 때 두 단어 모두 정렬한 뒤  정렬한 문자가 서로 같으면 true를 반환하면 될 것 같다고 생각 , 문제를 풀기 시작했다.

 << 세줄요약 >>
 1. 두 문자를 각 각 정렬한다.
 2. 두 문자를 비교한다
 3. 비교한 결과가 같으면 true, 아니면 false 반환하기 

😃 || 풀이 방법

import java.util.*;

class Solution {
    public boolean isAnagram(String s, String t) {
        boolean answer = true;

        if(!sortFunc(s).equals(sortFunc(t)))
          answer = false;


        return answer;
    }
    
    public String sortFunc(String word){
      char[] wordArr = word.toCharArray();

      Arrays.sort(wordArr);
      
      //처음에 구현했던 코드 , time limited 오류 
      //for(int i= 0; i<(wordArr.length -1); i++){
      //for(int j = i+1;j>0;j--){
      //    if(wordArr[j]<wordArr[j-1]){
      //        char temp=wordArr[j-1];
      //        wordArr[j-1]=wordArr[j];
      //        wordArr[j]=temp;
      //    }
      //}
      //}
      
      return String.valueOf(wordArr);
    }
}

처음에는 내가 직접 정렬 코드를 만들어 테스트를 진행했다.
테스트 케이스는 통과했지만 .. 제출을 하니 time limited 오류 발생!
검색해보니 내가 만든 정렬이 시간복잡도가 느린 버블 정렬이었다.

Arrays.sort 써서 통과!

✔ 정렬 다시 공부할 것 !

😃 || 코드 배우기

 

 

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()) return false;
        int[] count = new int[26];
        for(char ch:s.toCharArray()) count[ch-'a']++;
        for(char ch:t.toCharArray()){
            if(count[ch-'a']==0) return false;
            count[ch-'a']--;
        }
        return true;
    }
} 

가장 빠르게 풀리는 풀이법을 보고 배워보자

- 우선 문자열 길이가 다를 수 있다는 생각!
 문자열 길이가 다르면 가차없이 return false를 해준다.

- ch-'a' ?
 ASCII 코드를 보면 각 문자는 고유의 ASCII코드 값을 가진다. 
만약 ch의 값이 'a'라면 'a'-'a'는 0, count[0]의 숫자 카운트가 1 올라 갈 것이다
ch의 값이 'b'라면 'b' - 'a'는 1, count[1]의 숫자 카운트가 ++되어 1 올라갈 것이다.
즉 해당 알파벳을 각각 index로 생각해서 카운트를 올려주는 코드였던 것이다 

그 후 비교하려는 숫자의 각 알파벳의 ASCII코드를 가져오는데 
만약 위의 문자에 해당 알파벳이 있었다면 해당 알파벳의 count[index]의 값이 0이 될 수가 없다.
따라서 count[ch-'a']를 했을 때 0이 온다는 것은 같은 문자가 아니라는 뜻이고, false를 반환하는 것이다.