2023년 04월 28일 금요일 - 4월이 가기 전에 한 번 올립니다~
오늘 올려볼 문제는 839번 Similar String Groups 이라는 문제이다.
사진을 클릭하면 해당 문제로 이동합니다.
오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.
오늘 대체 문제가 더 어려웠다....
입력
사진에서도 볼 수 있듯이 string 배열이 입력으로 들어온다.
풀이 및 코드
string 2개를 비교했을 때 인덱스 2개에 해당하는 원소를 교체했을 때 같거나 처음부터 같다면 같은 집합에 포함한다고 했을 때 집합의 개수를 구하는 문제이다.
오늘은 처음부터 정답을 생각해냈다.
dfs로 직접 비교해가면서 문제를 풀었다.
또한 시간을 줄이기 위해서 set을 사용했다.
이제 코드를 봐보자!
풀이코드
class Solution {
HashSet<String> set = new HashSet<>();
String[] strs;
public int numSimilarGroups(String[] strs) {
this.strs = strs;
int result = 0;
for(var str: strs) {
if(set.contains(str)) continue;
solve(str);
result++;
}
return result;
}
private void solve(String str1) {
set.add(str1);
var arr1 = str1.toCharArray();
for(var str2: strs) {
if(set.contains(str2)) continue;
var arr2 = str2.toCharArray();
int diff = 0;
for(int i = 0; i < arr1.length && diff <= 2; i++)
if(arr1[i] != arr2[i]) diff++;
if(diff == 2) solve(str2);
}
}
}
제출 화면
오랜만에 블로그를 쓰는데 뭔가 느낌이 묘하다 ㅋㅋㅋ
내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.
'LeetCode 문제 풀이' 카테고리의 다른 글
| [LeetCode] 2101번 Detonate the Maximum Bombs 문제를 풀어보았다. (ft. java) (0) | 2023.06.02 |
|---|---|
| [LeetCode] 785번 Is Graph Bipartite? 문제를 풀어보았다. (ft. java) (0) | 2023.05.19 |
| [LeetCode] 1768번 Merge Strings Alternately 문제를 풀어보았다. (ft. java) (0) | 2023.04.18 |
| [LeetCode] 71번 Simplify Path 문제를 풀어보았다. (ft. java) (0) | 2023.04.12 |
| [LeetCode] 2390번 Removing Stars From a String 문제를 풀어보았다. (ft. java) (0) | 2023.04.11 |
