[LeetCode] 131. Palindrome Partitioning

😎풀이

해당 문제는 팰린드롬을 탐색해야 하는 문제이다.

다만 부분 문자열의 경우 백 트레킹 방식을 사용하여 재귀적으로 탐색해야 하므로 해당 방식을 채택하였음

function partition(s: string): string[][] {
    // 결과를 저장할 배열
    const result: string[][] = [];
    
    // 주어진 문자열이 팰린드롬인지 확인하는 헬퍼 함수
    function isPalindrome(start: number, end: number): boolean {
        while (start < end) {
            if (s[start] !== s[end]) return false;
            start++;
            end--;
        }
        return true;
    }
    
    // 백트래킹을 수행하는 재귀 함수
    function backtrack(start: number, current: string[]) {
        // 기저 사례: 문자열의 끝에 도달했을 때
        if (start >= s.length) {
            result.push([...current]); // 현재까지의 분할을 결과에 추가
            return;
        }
        
        // 현재 위치에서 가능한 모든 길이의 부분 문자열을 확인
        for (let end = start; end < s.length; end++) {
            // 현재 부분 문자열이 팰린드롬인 경우
            if (isPalindrome(start, end)) {
                // 현재 부분 문자열을 분할에 추가
                current.push(s.substring(start, end + 1));
                // 다음 위치에서 재귀적으로 탐색
                backtrack(end + 1, current);
                // 백트래킹: 현재 부분 문자열을 제거
                current.pop();
            }
        }
    }
    
    // 빈 배열로 시작하여 백트래킹 수행
    backtrack(0, []);
    return result;
}