[LeetCode] 131. Palindrome Partitioning

문제

https://leetcode.com/problems/palindrome-partitioning/description/

Palindrome Partitioning - LeetCode

 

Given a string s, partition s such that every substring of the partition is a palindrome(회문).
Return all possible palindrome partitioning of s.

주어진 문자열 s가 있을 때, 부분 문자열이 회문인 경우에만 처리합니다.

문자열 s의 가능한 모든 회문 파티션을 반환하세요.

* 회문이란?
앞으로 읽을 때나 뒤로 읽을 때 모두 같은 순서로 읽히는 문자열을 말합니다.
즉, 거꾸로 읽어도 원래의 문자열과 동일한 경우를 말합니다. "level", "radar", "noon" 등이 예시입니다.

 

 

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"
Output: [["a"]]

 

Constraints:

• 1 <= s.length <= 16
• s contains only lowercase English letters.

---

접근 방법

1. 어떤 알고리즘을 사용할까? 완전탐색(백트래킹) ➡ 시간복잡도 O(N * 2^N)

재귀적으로 문자열을 탐색하면서 가능한 모든 부분 문자열을 생성하고, 각 부분 문자열이 회문인지 확인할 예정입니다. 재귀 호출의 깊이는 문자열의 길이에 비례하므로 N이 되고 각 위치에서는 부분 문자열을 선택하거나 선택하지 않는 두 가지 선택이 이루어져 총 호출 수는 2^N입니다.

 

해당 문제에서 문자열의 길이는 최대 16이므로 대입해 보면, O(16 * 2^16) = 1,048,576입니다. 10⁸보다 작으므로 백트래킹으로 구현하기로 했습니다.

 

2. 코드 설계

  2-1. 만약 현재 위치가 문자열의 끝에 도달하면 현재까지의 경로를 결과에 추가하고 종료합니다.

  2-2. 현재 부분 문자열이 회문인 경우에만 처리합니다. ➡ 문자열의 각 부분 문자열을 path에 추가 ➡ 다음 인덱스로 재귀 호출하면서 마지막으로 추가된 부분 문자열을 제거합니다.(백트래킹)

 

코드구현

import java.util.*;

class PalindromePartitioning { 
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        backtrack(s, 0, new ArrayList<String>(), result);
        return result;
    }

    private void backtrack(String s, int start, List<String> path, List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < s.length(); i++) {
            if (isPalindrome(s, start, i)) {
                path.add(s.substring(start, i + 1));
                backtrack(s, i + 1, path, result);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int start, int end) { 
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}

 

배우게 된 점

1. char a = String.charAt(index i)

문자열의 인덱스i에 해당하는 문자를 출력

 

2. 백트래킹 부분을 메서드 안의 어느 위치에 넣을지 고민

디버깅을 통해 각 부분을 하나씩 이해하거나, 백트래킹 전후에 System.out.println()을 삽입하여 흐름을 이해하고 있습니다. 아직까지 시간이 많이 소요되고 있어서, 유사한 문제를 더 많이 풀어봐야 겠다는 생각을 했습니다.

// 백트래킹: 마지막으로 추가된 부분 문자열을 제거
path.remove(path.size() - 1);