LeetCode 131. Palindrome Partitioning 자바 문제 풀이

문제

Palindrome Partitioning - LeetCode

문제 해결 방법

-특정 스트링의 부분문자열 중에서 Palindrome만 찾는 문제입니다.

-Palindrome은 앞뒤를 뒤짚어도 똑같은 문자열 혹은 숫자를 뜻합니다. aba → aba

-모든 부분문자열을 찾고, 경우의 수들 중에서 Palindrome인 경우만 찾는것입니다.

-다만, 굳이 ‘모든’ 부분문자열을 찾을 필요는 없습니다. 앞쪽에서 이미 Palindrome이 아니라면, 나중에 나오는 조합역시 Palindrome이 아니기 때문입니다.

-abaabb의 부분문자열 중, abaa이후에 abaab이든 abaabb이든 Palindrome이 될수가 없습니다.

-그러므로 부분문자열을 찾는 알고리즘 중, 백트래킹을 사용하여, 이후에 나오는 조합을 찾지않음으로서 최적화를 할수 있습니다.

-부분문자열를 찾고, Palindrome이 아닐경우, 이후에 나오는 조합은 백트래킹 알고리즘으로 인해 스킵을 하고 다음 조합을 찾습니다.

1. 경우의 수를 백트래킹 알고리즘을 사용하여 탐색한다.
2. Palindrome이 아닐경우, 그 아래에 있는 조합식 트리는 스킵한다.
3. Palindrome이면 리스트에 저장한다.

시간복잡도: O(2^n), 공간복잡도: O(2^n)

https://github.com/eunhanlee/LeetCode_131_PalindromePartitioning_Solution.git

public class Solution {
    public List<List<String>> partition(String s) {
        return findSubstringsBacktracking(s);
    }

    /**
     * 백트래킹을 사용하여 주어진 입력 문자열의 모든 가능한 부분 문자열을 찾습니다.
     *
     * @param input 입력 문자열
     * @return 모든 가능한 부분 문자열을 포함하는 리스트의 리스트
     */
    public List<List<String>> findSubstringsBacktracking(String input) {
        List<List<String>> result = new ArrayList<>();
        findSubstringsBacktrackingRecur(input, 0, new ArrayList<>(), result);
        return result;
    }

    /**
     * 백트래킹을 사용하여 부분 문자열을 찾는 재귀적인 도움 메서드입니다.
     *
     * @param input   입력 문자열
     * @param start   부분 문자열 추출을 시작할 인덱스
     * @param current 현재 부분 문자열 조합
     * @param result  모든 유효한 부분 문자열 조합을 저장하는 리스트
     */
    private void findSubstringsBacktrackingRecur(String input, int start, List<String> current, List<List<String>> result) {
        // 시작 인덱스가 입력 문자열의 길이에 도달하면,
        // 모든 문자를 처리하고 유효한 부분 문자열 조합을 찾았습니다.
        // 현재 조합을 결과 리스트에 추가합니다.
        if (start == input.length()) {
            result.add(new ArrayList<>(current));
        }

        // 현재 시작 인덱스부터 가능한 모든 부분 문자열을 탐색합니다.
        for (int i = start; i < input.length(); i++) {
            // 시작 인덱스부터 현재 인덱스 i까지의 부분 문자열을 추출합니다.
            String substring = input.substring(start, i + 1);
            // 부분 문자열이 회문인 경우에만 현재 조합에 추가합니다.
            if (isPalindrome(substring)) {
                current.add(substring);
                // 재귀적으로 함수를 호출하여 문자열의 나머지 부분을 탐색합니다.
                // 다음 인덱스 (i + 1)부터 시작하고 현재 조합을 업데이트합니다.
                findSubstringsBacktrackingRecur(input, i + 1, current, result);
                // 마지막에 추가된 부분 문자열을 현재 조합에서 제거합니다.
                // 다음 반복에서 다른 가능성을 시도합니다.
                current.remove(current.size() - 1);
            }
        }
    }

    /**
     * 주어진 문자열이 회문Palindrome인지 확인합니다.
     *
     * @param input 확인할 입력 문자열
     * @return 입력 문자열이 회문Palindrome이면 true, 그렇지 않으면 false를 반환합니다.
     */
    private boolean isPalindrome(String input) {
        // null 또는 빈 입력인 경우에 대한 처리
        if (input == null || input.length() == 0) {
            return false;
        }

        // 왼쪽과 오른쪽 포인터를 초기화합니다.
        int left = 0;
        int right = input.length() - 1;

        // 왼쪽과 오른쪽 포인터에서 문자를 비교합니다.
        while (left < right) {
            // 문자가 다르면 회문이 아닙니다.
            if (input.charAt(left) != input.charAt(right)) {
                return false;
            }
            // 포인터를 가운데로 이동합니다.
            left++;
            right--;
        }

        // 반복문이 false를 반환하지 않으면 회문Palindrome입니다.
        return true;
    }
}

참조

부분문자열과 순열, 그리고 조합의 차이점, 경우의 수란?

backtracking 알고리즘이란?