資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學用 C++ 查詢最短超串
假設我們有一個字串陣列 A，我們需要找到一個包含 A 中每個字串作為子字串的最小字串。我們還可以假設 A 中沒有一個字串是另一個字串的子字串。
因此，如果輸入類似於 ["dbsh","dsbbhs","hdsb","ssdb","bshdbsd"]，則輸出將為 "hdsbbhssdbshdbsd"
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 calc()，它將接收 a、b 作為引數。
從 i := 0 開始，當 i < a 的大小，更新 (i 加 1)，執行：
如果從索引 i 到結尾的 a 的子字串位於 b 的開頭，則：
返回 b 的大小 - a 的大小 + i
返回 b 的大小
從主方法開始，執行以下步驟
ret := 空字串
n := A 的大小
定義一個大小為 n x n 的二維陣列 graph
從 j := 0 開始，當 j < n，更新 (j 加 1)，執行：
graph[i, j] := calc(A[i], A[j])
graph[j, i] := calc(A[j], A[i])
定義一個大小為 2^n x n 的陣列 dp。
定義一個大小為 2^n x n 的陣列 path。
minVal := inf
last := -1
從 i := 0 開始，當 i < 2^n，更新 (i 加 1)，執行：
從 j := 0 開始，當 j < n，更新 (j 加 1)，執行：
dp[i, j] := inf
從 i := 0 開始，當 i < 2^n，更新 (i 加 1)，執行：
從 j := 0 開始，當 j < n，更新 (j 加 1)，執行：
如果 i AND 2^j 非零，則
prev := i ^ (2^j)
如果 prev 等於 0，則：
dp[i, j] := A[j] 的大小
否則
從 k := 0 開始，當 k < n，更新 (k 加 1)，執行：
如果 prev AND 2^k 且 df[prev,k] 不為 inf 且 df[prev,k] + graph[k,j] < dp[i,j]，則
dp[i, j] := dp[prev, k] + graph[k, j]
path[i, j] := k
如果 i 等於 2^n - 1 且 dp[i, j] < minVal，則：
minVal := dp[i, j]
last := j
curr := 2^n - 1
定義一個棧 st
當 curr > 0 時，執行：
將 last 插入 st
temp := curr
curr := curr - (2^last)
last := path[temp, last]
i := st 的頂部元素
從 st 中刪除元素
ret := ret + A[i]
當 (st 不為空) 時，執行：
j := st 的頂部元素
從 st 中刪除元素
ret := ret 連線 A[j] 從 (A[j] 的大小 - graph[i,j] 到結尾) 的子字串
i := j
返回 ret
讓我們檢視以下實現以更好地理解：
示例
#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
307 次瀏覽
