[리트코드] 131. Palindrome Partitioning 회문

131. Palindrome Partitioning

문제

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

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. 현재 탐색 중인 문자열의 인덱스가 문자열의 길이와 동일한 경우 결과에 담는다.

2. 두 개의 포인터인 start와 end를 사용하여 중간으로 이동하면서 문자열이 회문인지 확인한다.

 

코드 구현

실패 코드

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

    public List<List<String>> backtracking(String s, int start, List<String> path, List<List<String>> result) {
        if(start == s.length()) {
            result.add(new ArrayList<>(path));
        }

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

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

이유:

1. 백트래킹 반환형이 잘못됨

  • List<List<String>> ➡️ void

2. 회문 평가하는 isPalindrome 메서드 이상함, 모든 경우의 수에 대해 검사해야 함

  • 문자열의 처음과 끝을 비교하며, 중간으로 이동하며 검사하는 걸로 수정

 

성공 코드

public class Solution {
    // 주어진 문자열 s에 대해 가능한 모든 회문 조합을 찾는 메서드
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>(); 
        backtracking(s, 0, new ArrayList<String>(), result); 
        return result; 
    }

    public void backtracking(String s, int start, List<String> path, List<List<String>> result) {
        // 만약 start 인덱스가 문자열 s의 길이와 같다면 모든 문자를 다 사용한 것이므로 결과에 추가
        if (start == s.length()) {
            result.add(new ArrayList<>(path)); 
            return;
        }

        // start 인덱스부터 문자열 s의 끝까지 반복
        for (int i = start; i < s.length(); i++) {
            // 현재 부분 문자열이 회문인지 확인
            if (isPalindrome(start, i, s)) {
                // 회문이면 경로에 추가
                path.add(s.substring(start, i + 1));
                // 다음 부분 문자열을 찾기 위해 백트래킹 호출
                backtracking(s, i + 1, path, result);
                // 백트래킹 이전 단계로 돌아가기 위해 경로에서 마지막 요소 제거
                path.remove(path.size() - 1);
            }
        }
    }

    // 주어진 문자열 s의 start 인덱스부터 end 인덱스까지가 회문인지 확인하는 메서드
    public boolean isPalindrome(int start, int end, String s) {
        while (start < end) {
            // 만약 현재 문자가 다르면 회문이 아님
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            // 다음 문자로 이동
            start++;
            end--;
        }
        return true; // 모든 문자가 일치하면 회문임
    }
}

  • 실행 시간 (Runtime): 8ms

  • 메모리 사용량 (Memory): 57.36MB

 

회고

리스트 넘길 때 이렇게 사용하자!

 public List<List<String>> partition(String s) {
    backtracking(new ArrayList<String>());
}

public List<List<String>> backtracking(List<String> path) {
    if(start == s.length()) {
        result.add(new ArrayList<>(path));
    }
}