(Leetcode) 242 - Valid Anagram
위 링크에 있는 문제들을 eazy 부터 시간이 있을때마다 풀어보려고 한다.
https://leetcode.com/problems/valid-anagram/description/
anagram은 같은 글자를 사용해 조합만 바뀐 형태를 의미한다.
내가 작성한 풀이
class Solution {
public boolean isAnagram(String s, String t) {
char[] temp1 = s.toCharArray();
char[] temp2 = t.toCharArray();
Arrays.sort(temp1);
Arrays.sort(temp2);
return Arrays.toString(temp1).equals(Arrays.toString(temp2));
}
}
문자열을 글자 단위로 쪼개 정령한 후 다시 합쳐 같은지 비교한다.
TC, SC
이 풀이의 시간 복잡도는 O(nlogn)이고, 공간 복잡도는 O(n)이다. nlogn 인 이유는 정렬이 들어가기 때문이다.
개선하기
마지막 부분을 다음과 같이 바꿔주면 string으로 바꾸지 않고도 비교할 수 있다.
return Arrays.equals(a,b);
다른 접근 방식
int[] count = new int[26];
// Count the frequency of characters in string s
for (char x : s.toCharArray()) {
count[x - 'a']++;
}
// Decrement the frequency of characters in string t
for (char x : t.toCharArray()) {
count[x - 'a']--;
}
// Check if any character has non-zero frequency
for (int val : count) {
if (val != 0) {
return false;
}
}
return true;
각 character의 사용횟수를 계산한다. 첫번째 입력값에 대해서는 사용될때마다 +1을 해주고, 두번째 입력값에 대해서는 사용될때마다 -1을 해준다. 처리한 후 0이 아닌 값이 있으면 동일하지 않다는 것이므로 false를 반환한다.
TC, SC
이 풀이의 시간 복잡도는 O(n)이고, 공간 복잡도는 O(1)이다. 공간 복잡도가 O(1)인 이유는 26이라는 고정된 크기를 가지기 때문이다.