회문 분할

난이도 중급
자주 묻는 질문 아마존 Facebook 구글 Microsoft
역 추적 깊이 우선 검색 동적 프로그래밍 조회수 26

문제 정책

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

예 

asaaaassss
2

설명 : 여기에서 입력 문자열을 다음과 같이자를 수 있습니다. 아사 | 아아아 | 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 배열입니다.

Translate »