Leetcode - 242. Valid Anagram : Easy

오늘의 문제는 이것입니다.

2개의 Strings가 input이고 그 두개의 문자열이 같은 문자들을 포함하고 있으면 (순서는 바뀌어도 됨) true 이고 아니면 false 입니다.

먼저 Pattern을 찾아 보겠습니다.

 

1. 두개의 입력값의 문자 개수가 같아야 한다. (Length of input strings should be same)

2. 입력값 1에 입력값 2에 없는 문자가 있으면 안된다. 그 반대도 안된다. (If input 1 has different letter than input 2 then false. Vibe versa)

3. 2개의 input에 문자열이 중복된 문자가 있으면 그 개수가 같아야 한다. (If the inputs have a letter multiple times then the count of the letter should be same)

 

그럼 우선 pattern 1 을 만족하는 로직을 만들어 보았다.

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] first = s.toCharArray();
        char[] second = t.toCharArray();
        boolean outPut = true;
        
        if(first.length != second.length) {
                outPut = false;
         }
        return outPut;
    }
}

 

이건 아주 간단한 로직이다.

두 input Strings를 charArray type으로 change 하고 그 배열의 개수를 비교해서 같으면 true이고 다르면 false 있다.

 

그럼 여기에 패턴 2를 만족 시키는 로직을 추가해 보았다.

 

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] first = s.toCharArray();
        char[] second = t.toCharArray();
        boolean outPut = true;
        
        char charLetter;
        String strLetter;
        char charLetter2;
        String strLetter2;

        if(first.length != second.length) {
                outPut = false;
         } else {
            for(int i=0; first.length > i; i++) {
                charLetter = first[i];
                strLetter = String.valueOf(charLetter);
                charLetter2 = second[i];
                strLetter2 = String.valueOf(charLetter2);
            
                if (t.contains(strLetter) && s.contains(strLetter2)){
                } else {
                    outPut = false;
                    break;
                }
            }
        } 
        return outPut;
    }
}

 

내가 만든 로직은 배열에 있는 글자 하나 하나 씩 불어와서 String으로 만든 후 그 글자가 서로 상대 입력 값에 있는지 여부를 체크 하도록 했다. 만약에 없다면 false 가 return 된다.

 

여기까지 하면 웬만한 건 다 체크 할 수 있다. 

하지만 두 입력 값이 같은 문자 들만 가지고 있는데 그 중 어떤 문자의 중복된 개수가 다를 경우 조건을 만족하지 못하게 된다.

 

 

이런 경우까지 만족 하려면 아래 로직을 추가 해야 한다.

 

        int[] sCounter = new int[26];
        int[] tCounter = new int[26];
        
        for (int i = 0; i < s.length(); i++) {
            sCounter[s.charAt(i) - 'a']++;
            tCounter[t.charAt(i) - 'a']++;
        }
        
        for (int i = 0; i < 26; i++) {
            if(sCounter[i] != tCounter[i]) {
                outPut = false;
            }
        }

 

여기에서는 ASCHII 코드에 대해 알아야 한다.

 

sCounter[s.charAt(i) - 'a']++; 를 한번 살펴 보자.

 

여기서 s = 'cac; 라고 가정하자.

 

c 의 ascii 코드 값은 99 다. a 는 97. 그러니까 s.charAt(I) - 'a' 는 99 - 97 이니까 2가 된다.

그럼 sCounter[2] 는 ++ 되서 1이 된다.

두번째 a 는 97-97이니까 sCount[0] 은 1이된다.

세번째 c는 다시 sCounter[2] 가 ++ 되서 2가 된다.

 

즉 각 문자가 몇번 증가 됐는지 파악 할 수 있다.

 

처음에 배열 개수를 26개로 정의 한 이유도 알파벳 개수는 26개 이기 때문이다.

 

전체 코드는 아래와 같다.

 

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] first = s.toCharArray();
        char[] second = t.toCharArray();
        boolean outPut = true;
        
        char charLetter;
        String strLetter;
        char charLetter2;
        String strLetter2;

        if(first.length != second.length) {
                outPut = false;
         } else {
            for(int i=0; first.length > i; i++) {
                charLetter = first[i];
                strLetter = String.valueOf(charLetter);
                charLetter2 = second[i];
                strLetter2 = String.valueOf(charLetter2);
            
                if (t.contains(strLetter) && s.contains(strLetter2)){
                } else {
                    outPut = false;
                    break;
                }
            }
        }
        
        int[] sCounter = new int[26];
        int[] tCounter = new int[26];
        
        for (int i = 0; i < s.length(); i++) {
            sCounter[s.charAt(i) - 'a']++;
            tCounter[t.charAt(i) - 'a']++;
        }
        
        for (int i = 0; i < 26; i++) {
            if(sCounter[i] != tCounter[i]) {
                outPut = false;
            }
        }
        
        return outPut;
    }
}

 

이렇게 만들고 보니까 맨 마지막 로직 으로  두번째 pattern 이 cover 되는 것 같다.

 

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

       If(s.length() != t.length()) {

           outPut = false;

           Return outPut;

       } 
        int[] sCounter = new int[26];
        int[] tCounter = new int[26];
        
        for (int i = 0; i < s.length(); i++) {
            sCounter[s.charAt(i) - 'a']++;
            tCounter[t.charAt(i) - 'a']++;
        }
        
        for (int i = 0; i < 26; i++) {
            if(sCounter[i] != tCounter[i]) {
                outPut = false;
            }
        }
        
        return outPut;
    }
}

 

과감하게 두번째 로직은 버리고 이렇게 하면 훨씬 짧은 코딩으로 결과를 만족 시킬 수 있다.

 

아래는 비슷한 접근 법인데 약간 다른 스크립트이다.

 

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    int[] table = new int[26];
    for (int i = 0; i < s.length(); i++) {
        table[s.charAt(i) - 'a']++;
    }
    for (int i = 0; i < t.length(); i++) {
        table[t.charAt(i) - 'a']--;
        if (table[t.charAt(i) - 'a'] < 0) {
            return false;
        }
    }
    return true;
}

 

일단 처리 속도를 생각해서 먼저 두 입력값 의 length를 비교해서 다르면 false를 return 해 버린다.

만약 같으면 그 아래를 실행 하게 되는데 ascii값을 이용해서 입력값 s의 문자들과 중복된 count를 table[]에 담는다.

 

그리고 for 문을 돌려 table에서 입력값 t에 있는 문자를 하나씩 가져와서 -1을 한다.

만약 그 값이 0보다 작으면 즉 마이너스가 되면 다른 문자이거나 같은 문자라도 그 숫자가 다르다는 것이기 때문에 false를 return 한다.

 

그리고 마지막으로 더 간단한 로직이 있다.

 

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    char[] str1 = s.toCharArray();
    char[] str2 = t.toCharArray();
    Arrays.sort(str1);
    Arrays.sort(str2);
    return Arrays.equals(str1, str2);
}

 

배열의 sort()메소드와 equals() 메소드를 사용하는 것이다.

요구조건을 잘 보면 두 입력값이 같은 문자들을 가지고 있는데 순서만 다르다는 거다.

즉 순서를 sorting 하면 두 입력 값은 정확히 일치하게 된다는 거다.

CharArray에는 equals()라는 메소드가 있으므로 이걸 사용해서 return 하면 깔끔하게 해결 된다.

 

따로 로직을 만들 필요 없이 배열의 sort() 와 equals()를 사용해서 해결 하면 된다.

 

또 한가지가 있다.

 

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    int[] counter = new int[26];
    for (int i = 0; i < s.length(); i++) {
        counter[s.charAt(i) - 'a']++;
        counter[t.charAt(i) - 'a']--;
    }
    for (int count : counter) {
        if (count != 0) {
            return false;
        }
    }
    return true;
}

 

첫번째 for loop에서는 입력값 s에 있는 문자들을 체크해서 counter에 ++ 하고

두번째 에서는 t 에 있는 문자들을 체크해서 counter에 -- 한다.

 

그러면 둘이 똑 같으면 counter 내에 있는 모든 값이 0이 되어야 하고 다르면 0 이외의 값이 될 것이다.