leetcode: Palindrome Partitioning

어차피 모든 경우의 수를 구하긴 해야한다.

하지만, 팰린드롬임을 한번 체크했다면 계속 그 글자가 팰린드롬인지 체크를 하지 않도록 어딘가 저장하는 방법은 없을지? => DP

 

팰린드롬 s의 서브스트링 s.substring(1, n-1) 또한 팰린드롬임을 이용하자.

=> DP[indexStart][indexEnd]: s.substring(indexStart, indexEnd)의 팰린드롬 여부

 

맨 첫 글자와 끝 글자가 같은 경우 중에서 팰린드롬이 될 수 있는 경우

1. 맨첫글자 위치 == 끝글자 위치 ex) "a"

2. 두 글자가 연속인 경우 ex) "aa"

3. 중간에 한 글자가 껴있는 경우 ex) "aba"

4. s.substring(첫 글자의 다음 글자, 끝 글자의 이전 글자)가 팰린드롬인 경우

 

 

import java.util.*;
class Solution {
	public List<List<String>> partition(String s) {
		List<List<String>> answer = new ArrayList<List<String>>();

		int length = s.length();
		boolean[][] dp = new boolean[length][length];

		palindrome(s, 0, answer, new Stack<String>(), dp);

		return answer;
	}

	public void palindrome(String s, int indexStart, List<List<String>> answer, Stack<String> currentList, boolean[][] dp) {
		if (indexStart >= s.length()) {
			answer.add(new ArrayList<>(currentList));
			return;
		}

		for (int end = indexStart; end < s.length(); end++) {
			if (s.charAt(indexStart) == s.charAt(end)) {
				if (end - 1 <= indexStart + 1 || dp[indexStart + 1][end - 1]) {
					dp[indexStart][end] = true;
					currentList.add(s.substring(indexStart, end + 1));
					palindrome(s, end + 1, answer, currentList, dp);
					currentList.pop();
				}
			}
		}
	}
}