[Leetcode] 131. Palindrome Partitioning

문제 요약

• 알고리즘 분류: 문자열, 백트레킹
• 난이도: Medium
• 문제내용:
  • 문자열 S가 주어지면 Palindrome 부분 문자열 목록들을 출력하라.
• 사이트 주소: https://leetcode.com/problems/palindrome-partitioning/description/

문제풀이

 이번 문제에는 백트레킹 관련 문제이다. 백트레킹 관련 자세한 내용은 아래 글에서 참고 하면된다.

https://jih3508.tistory.com/84

[알고리즘 이론] 백트래킹(Backtracking)

문제 접근방법

  Palindrome은 문자열뒤집었을때 같은 문자열을 말한다. 예를 들어 '기러기', '토마토' 같은 문자열이다. 이번 문제에서는 부분 문자열 슬라이싱하고 문자열 뒤집기만 하면 문제푸는데에 크게 지장이 없다. 구현 순서는 아래와 같이 하면 된다.

1. 파라미터는 정수 N과 리스트로 한다. 그리고 N은 0부터 시작한다.
2. N부터 해서 문자열 길이까지 반목문 i로 돌린다.
3. N부터 i까지 문자열을 추출하고 거꾸로 뒤집어서 같으면 리스트에 추가하고 i+1로 그 다음을 진행한다.
4. N이 문자열 길이가 같으면 목록을 추가한다.

Code

Python

class Solution:

    def partition(self, s: str) :
        self.s = s
        self.length = len(s)
        self.result = []
        self.backtracking(0)
        return self.result

    def backtracking(self, n , p = []):
        if(n == self.length):
            self.result.append(p)

        for i in range(n + 1, self.length + 1):
            string = self.s[n : i]
            # 문자열 같으면 리스트에 저장 하고 그 다음을 진행한다.
            if string == string[::-1]:
                self.backtracking(i, p + [string])


solution = Solution()
s = "aab"
print(solution.partition(s))
s = "a"
print(solution.partition(s))

• string[::-1]: [::-1]은 리스트또는 문자열을 거꾸로 한다.

Java

import java.util.ArrayList;
import java.util.List;

class Solution {
    List<List<String>> result;
	String s;
	int length;
	
	public List<List<String>> partition(String s) {
		this.s = s;
		this.length = s.length();
		this.result = new ArrayList<>();
		backtracking(0, new ArrayList<String>());
		
		return result;
    }
	
	public void backtracking(int n, ArrayList<String> p) {
		
		if (n == length) {
			List<String> add = new ArrayList<>();
			result.add(p);
		}
		
		String string;
		StringBuilder sb;
		for(int i = n + 1; i <= length; i++) {
			string = this.s.substring(n, i);
			sb = new StringBuilder(string);
            // 문자열 뒤집어서 같으면 추가 하고 그 다음 진행 한다.
			if(string.equals(sb.reverse().toString())) {
				p.add(string);
				backtracking(i,(ArrayList<String>) p.clone());
				p.remove(p.lastIndexOf(string));
			}
		}	
	}
}

• StringBuilder(String): 문자열 연결할때 쓰는 Class이다. 그리고 .reverse() 문자열 뒤집는 메소드도 제공해준다.
• (ArrayList<String>) p.clone(): CallByValue로 인하여 .clone을 사용한다. 안 그러면 목록안에 리스트도 값에 영향을 준다.
• p.remove(p.lastIndexOf(string)): 탐색이 끝나면 리시트의 마지막 인덱스를 지워 줘야 한다.