문자열 배열 A가 있다고 가정하고 A의 각 문자열을 부분 문자열로 포함하는 가장 작은 문자열을 찾아야 합니다. 또한 A에 있는 어떤 문자열도 A에 있는 다른 문자열의 부분 문자열이 아니라고 가정할 수 있습니다.
따라서 입력이 ["dbsh","dsbbhs","hdsb","ssdb","bshdbsd"]와 같으면 출력은 "hdsbbhssdbshdbsd"
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
calc() 함수를 정의하면, b,
-
initialize i :=0의 경우, i
-
인덱스 i에서 끝까지의 부분 문자열이 b의 시작에 있으면 -
-
b의 크기 반환 - + i의 크기
-
-
-
b
의 크기를 반환 -
기본 방법에서 다음 단계를 수행하십시오.
-
ret :=빈 문자열
-
n :=A의 크기
-
크기가 n x n −
인 하나의 2D 배열 그래프를 정의합니다.-
j 초기화의 경우:=0, j
-
그래프[i, j] :=calc(A[i], A[j])
-
그래프[j, i] :=calc(A[j], A[i])
-
-
-
2^n x n 크기의 배열 dp를 정의합니다.
-
2^n x n 크기의 배열 경로를 정의합니다.
-
minVal :=inf
-
마지막 :=-1
-
initialize i :=0의 경우, i <2^n일 때 업데이트(i를 1만큼 증가), 수행 -
-
j 초기화의 경우:=0, j
-
dp[i, j] :=정보
-
-
-
initialize i :=0의 경우, i <2^n일 때 업데이트(i를 1만큼 증가), 수행 -
-
j 초기화의 경우:=0, j
-
i AND 2^j가 0이 아니면
-
이전 :=나는 ^ (2^j)
-
-
prev가 0과 같으면 -
-
dp[i, j] :=A[j]의 크기
-
-
그렇지 않으면
-
초기화 k :=0의 경우 k
-
prev AND 2^k 및 df[prev,k]가 inf가 아니고 df[prev,k] +graph[k,j]
-
dp[i, j] :=dp[이전, k] + 그래프[k, j]
-
경로[i, j] :=k
-
-
-
-
-
i가 2^n - 1이고 dp[i, j]
-
minVal :=dp[i,j]
-
마지막 :=j
-
-
-
커 :=2^n - 1
-
하나의 스택 정의
-
curr> 0일 때 −
-
st에 마지막 삽입
-
임시 :=현재
-
curr :=curr - (2^마지막)
-
마지막 :=경로[임시, 마지막]
-
-
i :=st의 최상위 요소
-
st
에서 요소 삭제 -
렛 :=렛 + A[i]
-
동안(st가 비어 있지 않음) -
-
j :=st의 최상위 요소
-
st
에서 요소 삭제 -
ret :=ret A[j]의 부분 문자열을 (A[j]의 크기 - 그래프[i,j]에서 끝까지 연결)
-
나는 :=j
-
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int calc(string& a, string& b){
for (int i = 0; i < a.size(); i++) {
if (b.find(a.substr(i)) == 0) {
return b.size() - a.size() + i;
}
}
return (int)b.size();
}
string shortestSuperstring(vector<string>& A){
string ret = "";
int n = A.size();
vector<vector<int> > graph(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = calc(A[i], A[j]);
graph[j][i] = calc(A[j], A[i]);
}
}
int dp[1 << n][n];
int path[1 << n][n];
int minVal = INT_MAX;
int last = -1;
for (int i = 0; i < (1 << n); i++)
for (int j = 0; j < n; j++)
dp[i][j] = INT_MAX;
for (int i = 1; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if ((i & (1 << j))) {
int prev = i ^ (1 << j);
if (prev == 0) {
dp[i][j] = A[j].size();
} else {
for (int k = 0; k < n; k++) {
if ((prev & (1 << k)) && dp[prev][k] !=
INT_MAX && dp[prev][k] + graph[k][j] < dp[i][j]) {
dp[i][j] = dp[prev][k] + graph[k][j];
path[i][j] = k;
}
}
}
}
if (i == (1 << n) - 1 && dp[i][j] < minVal) {
minVal = dp[i][j];
last = j;
}
}
}
int curr = (1 << n) - 1;
stack<int> st;
while (curr > 0) {
st.push(last);
int temp = curr;
curr -= (1 << last);
last = path[temp][last];
}
int i = st.top();
st.pop();
ret += A[i];
while (!st.empty()) {
int j = st.top();
st.pop();
ret += (A[j].substr(A[j].size() - graph[i][j]));
i = j;
}
return ret;
}
};
main(){
Solution ob;
vector<string> v = {"dbsh","dsbbhs","hdsb","ssdb","bshdbsd"};
cout << (ob.shortestSuperstring(v));
} 입력
{"dbsh","dsbbhs","hdsb","ssdb","bshdbsd"} 출력
hdsbbhssdbshdbsd