공부한 것
- LeetCode #1763. Longest Nice Substring
- Divide and Conquer(분할 정복법)를 이해하기에 아주 좋은 다이어그램이 있어 가져와보았다:
해답 코드:
// Divide and Conquer 풀이: function longestNiceSubstring2(s: string): string { // 탈출 조건: s의 길이가 0 혹은 1인 경우, 대-소문자 짝이 있을 수 없으므로 (최장 부분 문자열은)빈 문자열 반환. if (s.length < 2) return ''; let arr = [...s]; let set = new Set(arr); for (let i = 0; i < arr.length; i++) { const c = arr[i]; // 현재 문자 c의 대소문자 버전이 모두 현재 부분 문자열 s에 존재하면: 현재 부분 문자열 s의 다음 문자 검사를 계속한다(=s를 둘로 쪼개지 않는다). if (set.has(c.toUpperCase()) && set.has(c.toLowerCase())) continue; // 현재 문자 c의 대소문자가 현재 부분 문자열 s에 들어있지 않으면: 현재 문자 c를 기준으로 반절을 가른 부분 문자열 각각에서 최장 부분 문자열을 추출한다. s의 길이가 < 2에 도달할 때까지 반복하게 됨. const sub1: string = longestNiceSubstring2(s.substring(0, i)); const sub2: string = longestNiceSubstring2(s.substring(i + 1)); // 두 (최장)부분 문자열 중 길이가 더 긴 쪽을 반환한다. return sub1.length >= sub2.length ? sub1 : sub2; } return s; }
Uploaded by N2T