회문 분할


난이도 중급
자주 묻는 질문 아마존 페이스북 서비스 구글 Microsoft
역 추적 깊이 우선 검색 동적 프로그래밍

문제 정책

문자열이 주어지면 파티션의 모든 하위 문자열이 회문이되도록 필요한 최소 절단 수를 찾으십시오. 모든 부분 문자열이 회문이되도록 원래 문자열을 다른 파티션으로 자르기 때문에이 문제를 회문 파티션 문제라고합니다.

예 

asaaaassss
2

설명 : 여기에서 입력 문자열을 다음과 같이자를 수 있습니다. asa | aaa | ssss, 따라서 두 번의 절단이 필요합니다.

zxxzxxzyuy
1

설명 : 여기에서 입력 문자열을 다음과 같이자를 수 있습니다. zxxzxxz | 유이, 따라서 단일 컷이 필요합니다.

 

회문 분할을위한 접근 방식

순진한 접근

가장 먼저 떠오르는 것은 간단한 재귀 솔루션입니다. 길이가 n이라는 문자열이 있다고 생각해보십시오. 이제 문자열이 회문이면 간단히 답을 0으로 반환 할 수 있지만 회문이 아닌 경우에는 대답합니다. 우리는 모든 가능성을 시도합니다. 즉, k 번째 인덱스에서 두 개의 분할 영역으로 문자열을 잘라낸 다음 왼쪽 부분과 오른쪽 부분을 개별적으로 재귀 적으로 해결하려고합니다. 이 솔루션은 절대적으로 정확하지만 효율적이지 않습니다.

minCut(string s, int i, int j) = 1 + min( minCut(s, i, k) + minCut(s, k+1, j) )

where k ranges from i to j

i, j, k are indices on string

회문 분할

효율적인 접근

지금까지 우리는 현의 왼쪽 부분과 오른쪽 부분을 해결하면서 그 사이에 컷을 배치하는 간단한 솔루션을 알고 있습니다. 그래서 우리는 처음에 우리가 크기 n의 문자열에 문제가 있었다고 말할 수 있습니다. 그리고 우리는 문제를 두 개의 하위 문제로 줄였습니다. 하위 문제의 구조를 보면 그것들도 확실히 겹칩니다. 그래서 이것은 동적 프로그래밍 이전 솔루션의 기하 급수적 인 시간 복잡성을 줄여 O (N ^ 3). 그림은 겹치는 하위 문제를 빨간색으로 보여줍니다. 비슷한 동적 프로그래밍 패턴을 볼 수 있습니다 행렬 연쇄 곱셈 문제, 먼저 작은 하위 문제를 해결 한 다음 그 결과를 결합하여 원래 문제를 해결합니다.

회문 분할을위한 코드

C ++ 코드

#include <bits/stdc++.h>
using namespace std;

int minCut(string s) {
    int n = s.length();
    vector<vector<int>> cuts;
    vector<vector<bool>> isPalindrome;
    cuts.assign(n,vector<int>(n, INT_MAX));
    isPalindrome.assign(n, vector<bool>(n, false));
    
    for(int len = 1;len<=n;len++) {
        for(int i=0;i<n-len+1;i++) {
            int j = i+len-1;
            if(len <= 2)
                isPalindrome[i][j] = s[i] == s[j];
            else
                isPalindrome[i][j] = s[i] == s[j] && isPalindrome[i+1][j-1];
            
            if(isPalindrome[i][j]) {
                cuts[i][j] = 0;
            } else {
                for(int k=i;k<j;k++)
                    cuts[i][j] = min(cuts[i][j], 1+cuts[i][k]+cuts[k+1][j]);
            }
        }
    }
    return cuts[0][n-1];
}

int main() {
  int t;cin>>t;
  while(t--){
      string s;
      cin>>s;
      cout<<minCut(s)<<endl;
  }
}

자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static int minCut(String s) {
        int n = s.length();
        int cuts[][] = new int[n][n];
        boolean isPalindrome[][] = new boolean[n][n];
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cuts[i][j] = Integer.MAX_VALUE;
            }
        }
        
        for(int len = 1;len<=n;len++) {
            for(int i=0;i<n-len+1;i++) {
                int j = i+len-1;
                if(len <= 2)
                    isPalindrome[i][j] = s.charAt(i) == s.charAt(j);
                else
                    isPalindrome[i][j] = s.charAt(i) == s.charAt(j) && isPalindrome[i+1][j-1];
                
                if(isPalindrome[i][j]) {
                    cuts[i][j] = 0;
                } else {
                    for(int k=i;k<j;k++)
                        cuts[i][j] = Math.min(cuts[i][j], 1+cuts[i][k]+cuts[k+1][j]);
                }
            }
        }
        return cuts[0][n-1];    
    }
    
  public static void main (String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());
    while(t-- > 0) {
        String s = br.readLine();
        int ans = minCut(s);
        System.out.println(ans);
    }
  }
}

시간 복잡도 : O (N ^ 3)

첫 번째 루프는 1에서 n까지 실행됩니다 (len = 1 ~ len = n).

하위 문제 (i)의 시작 인덱스를 나타내는 중첩 루프는 0에서 n-len까지 실행됩니다.

k와 k + 1 사이의 절단 인덱스를 나타내는 가장 안쪽 루프도 i에서 j까지 이어집니다. 

따라서 최악의 경우 시간 복잡도는 O (N ^ 3)라고합니다.

공간 복잡성 : O (N ^ 2)

두 개의 배열 isPalindrome과 2D 배열 인 컷이 있으므로 O (N ^ 2) 공간 복잡성이 있습니다.

 

회문 분할을위한 최적화 된 솔루션

시간 복잡성을 더욱 줄일 수 있습니다. O (N ^ 2), isPalindrome 행렬을 미리 계산합니다. 그런 다음 i에서 j (i는 왼쪽 경계이고 j는 회문 하위 문자열의 오른쪽 경계)에서 하위 문자열에 대한 컷을 저장하는 대신 컷을 하위 문자열 시작에 필요한 최소 컷 수를 저장하는 0 차원 배열로 저장합니다. 0에서 i. 내부 루프는 j에서 1에서 i-0까지 실행됩니다. 여기서 하위 문자열 [j, i]가 회문인지 확인합니다. 부분 문자열이 회문이면 부분 문자열 [j, i]는 부분 문자열 [1, j-1] + 0과 동일한 수의 컷을가집니다. 따라서 j에 대한 모든 옵션의 최소값을 저장하여 답을 업데이트합니다. 1에서 i-XNUMX. 이렇게하면 결국 모든 파티션이 회문이되도록 필요한 최소 절단 수를 갖게됩니다.

C ++ 코드

#include <bits/stdc++.h>
using namespace std;

int minCut(string s) {
    int n = s.length();
    vector<int> cuts;
    vector<vector<bool>> isPalindrome;
    cuts.assign(n,INT_MAX);
    isPalindrome.assign(n, vector<bool>(n, false));
    
    for(int len = 1;len<=n;len++) {
        for(int i=0;i<n-len+1;i++) {
            int j = i+len-1;
            if(len <= 2)
                isPalindrome[i][j] = s[i] == s[j];
            else
                isPalindrome[i][j] = s[i] == s[j] && isPalindrome[i+1][j-1];
        }
    }
    
    cuts[0] = 0;
    for(int i=1;i<n;i++) {
        for(int j=1;j<=i;j++)
            if(isPalindrome[0][i])
                cuts[i] = 0;
            else if(isPalindrome[j][i])
                cuts[i] = min(cuts[i], 1 + cuts[j-1]);
    }
    return cuts[n-1];
}

int main() {
  int t;cin>>t;
  while(t--){
      string s;
      cin>>s;
      cout<<minCut(s)<<endl;
  }
}

자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static int minCut(String s) {
        int n = s.length();
        int cuts[] = new int[n];
        boolean isPalindrome[][] = new boolean[n][n];
        
        for(int i=0;i<n;i++) {
            cuts[i] = Integer.MAX_VALUE;
        }
        
        for(int len = 1;len<=n;len++) {
            for(int i=0;i<n-len+1;i++) {
                int j = i+len-1;
                if(len <= 2)
                    isPalindrome[i][j] = s.charAt(i) == s.charAt(j);
                else
                    isPalindrome[i][j] = s.charAt(i) == s.charAt(j) && isPalindrome[i+1][j-1];
            }
        }
        
        cuts[0] = 0;
        for(int i=1;i<n;i++) {
            for(int j=1;j<=i;j++)
                if(isPalindrome[0][i])
                    cuts[i] = 0;
                else if(isPalindrome[j][i])
                    cuts[i] = Math.min(cuts[i], 1 + cuts[j-1]);
        }
        return cuts[n-1];
    }
    
  public static void main (String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());
    while(t-- > 0) {
        String s = br.readLine();
        int ans = minCut(s);
        System.out.println(ans);
    }
  }
}

시간 복잡성: O (N ^ 2)

인덱스에서 j까지의 하위 문자열이 회문이면 저장을 위해 O (N ^ 2)를 사용했습니다.

최소 절단 수를 찾기위한 O (N ^ 2). 외부 루프는 문자열의 전체 길이에 걸쳐 실행되고 내부 루프는 0에서 i-1까지 실행됩니다.

따라서 런타임은 총 O (N ^ 2)가됩니다.

공간 복잡성: O (N ^ 2)

cuts 배열은 이제 2 차원이지만 isPalindrome은 여전히 ​​XNUMXD 배열입니다.