[leetcode] 131. Palindrome Partitioning

문제 : https://leetcode.com/problems/palindrome-partitioning/

---

문자열 s가 입력으로 주어지면 파티션의 모든 하위 문자열이 palidrome 이 되도록 하는 모든 경우를 구하라.

문자열을 앞뒤로 읽었을 때 같은 문자열인 경우 palidrome이라 한다.

---

DP + backtracking

 

팰린드롬인지 구하는 함수. DP

// dp[s][e] = str[s ~ e]가 palidrome인지
fun isPalidrome(str, s, e) {
	if(dp[s][e]가 없으면) 
	    dp[s][e] = str[s]와 str[e]가 같은 문자이며 isPalidrome(str, s+1, s-1) 인 경우
    return dp[s][e];
}

 

팰린드롬 하위 문자열들을 만들어서 partitions 배열을 만드는 함수. backtracking

정답가능한 partitions인 경우 정답 배열 answer에 추가한다.

/**
 * str[s~] 문자열을 팰린드롬 부분문자열 리스트를 만들어 partitions에 추가한다.
 * partitions : 이때까지 방문한 팰린드롬 부분문자열 리스트
 */
void dfs(string& str, int s, vector<string>& partitions) {
	if(s == n) // 문자열의 마지막까지 탐색한 경우 -> 정답
    	answer.push_back(partitions); // 추가

	for(int e = s; e < n; e++) {
    	// 팰린드롬인 경우
    	if(isPalindrome(str, s, e)){            
            partitions.push_back(str.substr(s, e-s+1));
            dfs(str, e+1, partitions);
            partitions.pop_back();
        }
    }
}

 

시간복잡도는 O(2^N * N). N = |입력문자열|

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/131.%20Palindrome%20Partitioning.cpp