leeyupeng

leeyupeng@126.com

0%

leetcode.943. 最短超级串

发表于 更新于 分类于 ， 阅读次数： Valine：

最短超级串

问题描述

给定一个字符串数组 A，找到以 A 中每个字符串作为子字符串的最短字符串。

我们可以假设 A 中没有字符串是 A 中另一个字符串的子字符串。

示例 1：

输入：[“alex”,”loves”,”leetcode”]
输出：”alexlovesleetcode”
解释：”alex”，”loves”，”leetcode” 的所有排列都会被接受。
示例 2：

输入：[“catg”,”ctaagt”,”gcta”,”ttca”,”atgcatc”]
输出：”gctaagttcatgcatc”

矩阵全排列

思路分析

  • 1.Matrix[i][j] 记录 i,j连接可以重叠的字母数量
  • 2.0-n 全排列找出最小答案
  • 3.全排列剪枝，当前条件下，重叠字母数量总和小于已经求出的解时 剪枝

执行用时 :100 ms, 在所有 C++ 提交中击败了55.43%的用户
内存消耗 :9 MB, 在所有 C++ 提交中击败了100.00%的用户

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
class Solution {
public:
	vector<string> AA;
	int n;
	int maxlength;
	vector<vector<int>> matrix;

	string ans;
	vector<int> vmaxcount;
	int maxcountall;
	int anscount = INT32_MIN;
	int count = 0;
	void Perm(vector<int>& v, int k,int length,int maxcount)
	{
		if (k == n - 1) {
			if (k != 0) { count += matrix[v[k - 1]][v[k]]; }
			if (anscount >= count) {}
			else {
				anscount = count;
				string s = AA[v[0]];
				for (int i = 1; i < n; i++) {
					s.append(AA[v[i]].substr(matrix[v[i - 1]][v[i]], AA[v[i]].length() - matrix[v[i - 1]][v[i]]));
				}

				if (ans.empty() || ans.length() > s.length()) { ans = s; }
			}
			if (k != 0) { count -= matrix[v[k - 1]][v[k]]; };
		}
		else if(k == 0){
			for (int i = k; i < n; i++)
			{
				swap(v[k], v[i]);
				length += AA[v[k]].length();
				maxcount -= vmaxcount[v[k]];
				Perm(v,k+1,length, maxcount);
				maxcount += vmaxcount[v[k]];
				length -= AA[v[k]].length();
				swap(v[k], v[i]);
			}
		}
		else {
			for (int i = k; i < n; i++)
			{
				swap(v[k], v[i]);
				count += matrix[v[k - 1]][v[k]];
				length += AA[v[k]].length();
				maxcount -= vmaxcount[v[k]];
				if (maxcount + count <= anscount) {
				}
				else {
					Perm(v, k + 1, length,maxcount);
				}
				maxcount += vmaxcount[v[k]];
				length -= AA[v[k]].length();
				count -= matrix[v[k - 1]][v[k]];
				swap(v[k], v[i]);
			}
		}
	}

	string shortestSuperstring(vector<string>& A) {
		vector<int> substring;
		for (int i = 0; i < A.size(); i++){
			for (int j = 0; j < A.size(); j++) {
				if (i != j && A[i].length() <= A[j].length()) {
					if (A[j].find(A[i]) != string::npos) {
						substring.push_back(i);
						break;
					}
				}
			}
		}
		while (!substring.empty())
		{
			A.erase(A.begin()+substring.back());
			substring.pop_back();
		}
		AA = A;
		n = A.size();

		maxlength = 0;
		for (int i = 0; i < n; i++) { maxlength += A[i].length(); }

		matrix.insert(matrix.begin(), n, {});
		for (int i = 0; i < n; i++) {
			matrix[i].insert(matrix[i].begin(), n, 0);
		}

		int count = 0;
		int k;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i != j) {
					count = min(A[i].length(), A[j].length());
					while (count > 0)
					{
						for (k = 0; k < count; k++)
						{
							if (A[i][A[i].length() - count + k] == A[j][k]) { continue; }
							else { break; }
						}
						if (k == count) { break; }
						count--;
					}
					matrix[i][j] = count;
				}
			}
		}
		vmaxcount.insert(vmaxcount.begin(), n, 0);

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				vmaxcount[i] = max(vmaxcount[i],matrix[i][j]);
				vmaxcount[j] = max(vmaxcount[j], matrix[i][j]);
			}
		}
		maxcountall = 0;
		for (int i = 0; i < n; i++) {
			maxcountall += vmaxcount[i];
		}

		vector<int> perm(n);
		for (int i = 0; i < n; i++)
		{
			perm[i] = i;
		}
		Perm(perm,0,0,maxcountall);
 		return ans;
	}
};

代码实现

优化 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
class Solution {
public:
	vector<string> AA;
	int n;
	int maxlength;
	vector<vector<int>> matrix;

	vector<int> vans;
	string ans;
	vector<int> vmaxcount;
	int maxcountall;
	int anscount = INT32_MIN;
	int count = 0;
	void Perm(vector<int>& v, int k, int length, int maxcount)
	{
		if (k == n - 1) {
			if (k != 0) { count += matrix[v[k - 1]][v[k]]; }
			if (anscount >= count) {}
			else {
				anscount = count;
				vans = v;
			}
			if (k != 0) { count -= matrix[v[k - 1]][v[k]]; };
		}
		else if (k == 0) {
			for (int i = k; i < n; i++)
			{
				swap(v[k], v[i]);
				length += AA[v[k]].length();
				maxcount -= vmaxcount[v[k]];
				Perm(v, k + 1, length, maxcount);
				maxcount += vmaxcount[v[k]];
				length -= AA[v[k]].length();
				swap(v[k], v[i]);
			}
		}
		else {
			for (int i = k; i < n; i++)
			{
				swap(v[k], v[i]);
				count += matrix[v[k - 1]][v[k]];
				length += AA[v[k]].length();
				maxcount -= vmaxcount[v[k]];
				if (maxcount + count <= anscount) {
				}
				else {
					Perm(v, k + 1, length, maxcount);
				}
				maxcount += vmaxcount[v[k]];
				length -= AA[v[k]].length();
				count -= matrix[v[k - 1]][v[k]];
				swap(v[k], v[i]);
			}
		}
	}

	string shortestSuperstring(vector<string>& A) {
		vector<int> substring;
		for (int i = 0; i < A.size(); i++) {
			for (int j = 0; j < A.size(); j++) {
				if (i != j && A[i].length() <= A[j].length()) {
					if (A[j].find(A[i]) != string::npos) {
						substring.push_back(i);
						break;
					}
				}
			}
		}
		while (!substring.empty())
		{
			A.erase(A.begin() + substring.back());
			substring.pop_back();
		}
		AA = A;
		n = A.size();

		maxlength = 0;
		for (int i = 0; i < n; i++) { maxlength += A[i].length(); }

		matrix.insert(matrix.begin(), n, {});
		for (int i = 0; i < n; i++) {
			matrix[i].insert(matrix[i].begin(), n, 0);
		}

		int count = 0;
		int k;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i != j) {
					count = min(A[i].length(), A[j].length());
					while (count > 0)
					{
						for (k = 0; k < count; k++)
						{
							if (A[i][A[i].length() - count + k] == A[j][k]) { continue; }
							else { break; }
						}
						if (k == count) { break; }
						count--;
					}
					matrix[i][j] = count;
				}
			}
		}
		vmaxcount.insert(vmaxcount.begin(), n, 0);

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				vmaxcount[i] = max(vmaxcount[i], matrix[i][j]);
				vmaxcount[j] = max(vmaxcount[j], matrix[i][j]);
			}
		}
		maxcountall = 0;
		for (int i = 0; i < n; i++) {
			maxcountall += vmaxcount[i];
		}

		vector<int> perm(n);
		for (int i = 0; i < n; i++)
		{
			perm[i] = i;
		}
		Perm(perm, 0, 0, maxcountall);


		string s = AA[vans[0]];
		for (int i = 1; i < n; i++) {
			s.append(AA[vans[i]].substr(matrix[vans[i - 1]][vans[i]], AA[vans[i]].length() - matrix[vans[i - 1]][vans[i]]));
		}
		if (ans.empty() || ans.length() > s.length()) { ans = s; }
		return ans;
	}
};

动态规划(组合)

思路分析

dp[i][j] 代表 组合i，以j为末尾的最优解

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
class Solution {
public:
	vector<string> AA;
	int n;
	int maxlength;
	vector<vector<int>> matrix;

	string shortestSuperstring(vector<string>& A) {
		vector<int> substring;
		for (int i = 0; i < A.size(); i++){
			for (int j = 0; j < A.size(); j++) {
				if (i != j && A[i].length() <= A[j].length()) {
					if (A[j].find(A[i]) != string::npos) {
						substring.push_back(i);
						break;
					}
				}
			}
		}
		while (!substring.empty())
		{
			A.erase(A.begin()+substring.back());
			substring.pop_back();
		}
		AA = A;
		n = A.size();

		maxlength = 0;
		for (int i = 0; i < n; i++) { maxlength += A[i].length(); }

		matrix.insert(matrix.begin(), n, {});
		for (int i = 0; i < n; i++) {
			matrix[i].insert(matrix[i].begin(), n, 0);
		}

		int count = 0;
		int k;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i != j) {
					count = min(A[i].length(), A[j].length());
					while (count > 0)
					{
						for (k = 0; k < count; k++)
						{
							if (A[i][A[i].length() - count + k] == A[j][k]) { continue; }
							else { break; }
						}
						if (k == count) { break; }
						count--;
					}
					matrix[i][j] = count;
				}
			}
		}

		vector<vector<string>> dp(1<<(n));
		for (int i = 0; i < 1 << (n); i++) {
			dp[i].insert(dp[i].begin(), n, "");
		}
		vector<int> * last = new vector<int>();
		for (int i = 0; i < n; i++) {
			dp[1 << i][i] = A[i];
			last->push_back(1<<i);
		}
		set<int> tempset;
		vector<int> *temp = new vector<int>();
		string stemp;
		int value;
		int valuej;
		for (int k = 1; k < n; k++) {
			for (int i = 0; i < last->size(); i++) {
				value = (*last)[i];
				for (int j = 0; j < n; j++) {
					if (((1 << j) & value) == 0) {
						valuej = value + (1 << j);
						for (int ii = 0; ii < n; ii++) {
							if (((1 << ii) & value) != 0) {
								if (dp[valuej][j] == "") {
									dp[valuej][j] = dp[value][ii];
									dp[valuej][j].append(A[j].substr(matrix[ii][j], A[j].length() - matrix[ii][j]));
								}
								else
								{
									if(dp[valuej][j].length() > dp[value][ii].length() + A[j].length() - matrix[ii][j]){
										stemp = dp[value][ii];
										stemp.append(A[j].substr(matrix[ii][j], A[j].length() - matrix[ii][j]));
										dp[valuej][j] = stemp;
									}
								}
							}
						}
						if (!(tempset.find(valuej) != tempset.end())) {
							temp->push_back(valuej);
							tempset.insert(valuej);
						}
					}

				}
			}
			vector<int> * ttemp = last;
			last = temp;
			temp = ttemp;
			temp->clear();
			tempset.clear();
		}
		int valueans = (1 << n) - 1;
		string ans= dp[valueans][0];
		for (int i = 1; i < n; i++) {
			if (ans.length() > dp[valueans][i].length()) {
				ans = dp[valueans][i];
			}
		}
 		return ans;
	}
};

代码实现

优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
class Solution {
public:
	vector<string> AA;
	int n;
	int maxlength;
	vector<vector<int>> matrix;

	string shortestSuperstring(vector<string>& A) {
		vector<int> substring;
		for (int i = 0; i < A.size(); i++){
			for (int j = 0; j < A.size(); j++) {
				if (i != j && A[i].length() <= A[j].length()) {
					if (A[j].find(A[i]) != string::npos) {
						substring.push_back(i);
						break;
					}
				}
			}
		}
		while (!substring.empty())
		{
			A.erase(A.begin()+substring.back());
			substring.pop_back();
		}
		AA = A;
		n = A.size();

		maxlength = 0;
		for (int i = 0; i < n; i++) { maxlength += A[i].length(); }

		matrix.insert(matrix.begin(), n, {});
		for (int i = 0; i < n; i++) {
			matrix[i].insert(matrix[i].begin(), n, 0);
		}

		int count = 0;
		int k;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i != j) {
					count = min(A[i].length(), A[j].length());
					while (count > 0)
					{
						for (k = 0; k < count; k++)
						{
							if (A[i][A[i].length() - count + k] == A[j][k]) { continue; }
							else { break; }
						}
						if (k == count) { break; }
						count--;
					}
					matrix[i][j] = count;
				}
			}
		}

		vector<vector<int>> dp(1<<(n));
		for (int i = 0; i < 1 << (n); i++) {
			dp[i].insert(dp[i].begin(), n, 0);
		}

		vector<vector<int>> parent(1 << (n));
		for (int i = 0; i < 1 << (n); i++) {
			parent[i].insert(parent[i].begin(), n, -1);
		}
		vector<int> * last = new vector<int>();
		for (int i = 0; i < n; i++) {
			dp[1 << i][i] = 0;
			last->push_back(1<<i);
		}
		set<int> tempset;
		vector<int> *temp = new vector<int>();
		string stemp;
		int value;
		int valuej;
		for (int k = 1; k < n; k++) {
			for (int i = 0; i < last->size(); i++) {
				value = (*last)[i];
				for (int ii = 0; ii < n; ii++) {
					if (((1 << ii) & value) != 0) {
						for (int j = 0; j < n; j++) {
							if (((1 << j) & value) == 0) {
								valuej = value + (1 << j);

								if (parent[valuej][j] == -1) {
									dp[valuej][j] = dp[value][ii] + matrix[ii][j];
									parent[valuej][j] = ii;
								}
								else if (dp[valuej][j] < dp[value][ii] + matrix[ii][j]) {
									dp[valuej][j] = dp[value][ii] + matrix[ii][j];
									parent[valuej][j] = ii;
								}
								if (!(tempset.find(valuej) != tempset.end())) {
									temp->push_back(valuej);
									tempset.insert(valuej);
								}
							}

						}

					}

				}
			}
			vector<int> * ttemp = last;
			last = temp;
			temp = ttemp;
			temp->clear();
			tempset.clear();
		}
		vector<int> ansindex(n);
		int p = 0;
		int p2;
		int valueans = (1 << n) - 1;
		for (int i = 1; i < n; i++) {
			if (dp[valueans][p] < dp[valueans][i]) {
				p = i;
			}
		}
		int mask = valueans;
		int t = n;
		while (p != -1) {
			ansindex[--t] = p;
			p2 = parent[mask][p];
			mask ^= 1 << p;
			p = p2;
		}

		string ans= A[ansindex[0]];
		int ii = ansindex[0];
		for (int i = 1; i < n; i++) {
			int j = ansindex[i];
			ans.append(A[j].substr(matrix[ii][j], A[j].length() - matrix[ii][j]));
			ii = j;
		}
 		return ans;
	}
};

代码实现

优化 组合数 从0到1<<n计算 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
class Solution {
public:
	vector<string> AA;
	int n;
	int maxlength;
	vector<vector<int>> matrix;

	string shortestSuperstring(vector<string>& A) {
		vector<int> substring;
		for (int i = 0; i < A.size(); i++){
			for (int j = 0; j < A.size(); j++) {
				if (i != j && A[i].length() <= A[j].length()) {
					if (A[j].find(A[i]) != string::npos) {
						substring.push_back(i);
						break;
					}
				}
			}
		}
		while (!substring.empty())
		{
			A.erase(A.begin()+substring.back());
			substring.pop_back();
		}
		AA = A;
		n = A.size();

		maxlength = 0;
		for (int i = 0; i < n; i++) { maxlength += A[i].length(); }

		matrix.insert(matrix.begin(), n, {});
		for (int i = 0; i < n; i++) {
			matrix[i].insert(matrix[i].begin(), n, 0);
		}

		int count = 0;
		int k;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i != j) {
					count = min(A[i].length(), A[j].length());
					while (count > 0)
					{
						for (k = 0; k < count; k++)
						{
							if (A[i][A[i].length() - count + k] == A[j][k]) { continue; }
							else { break; }
						}
						if (k == count) { break; }
						count--;
					}
					matrix[i][j] = count;
				}
			}
		}

		vector<vector<int>> dp(1<<(n));
		for (int i = 0; i < 1 << (n); i++) {
			dp[i].insert(dp[i].begin(), n, 0);
		}

		vector<vector<int>> parent(1 << (n));
		for (int i = 0; i < 1 << (n); i++) {
			parent[i].insert(parent[i].begin(), n, -1);
		}
		vector<int> * last = new vector<int>();
		for (int i = 0; i < n; i++) {
			dp[1 << i][i] = 0;
			last->push_back(1<<i);
		}
		set<int> tempset;
		vector<int> *temp = new vector<int>();
		string stemp;
		int pmask;
		for (int mask = 0; mask < (1 << n); mask++) {
			for (int j = 0;j < n; j++) {
				if (((1 << j) & mask) != 0) {
					pmask = mask ^ (1 << j);
					if (pmask == 0) { continue; }
					for (int i = 0; i < n; i++) {
						if (((1 << i) & pmask) != 0) {
							if (parent[mask][j] == -1) {
								dp[mask][j] = dp[pmask][i] + matrix[i][j];
								parent[mask][j] = i;
							}
							else if (dp[mask][j] < dp[pmask][i] + matrix[i][j]) {
								dp[mask][j] = dp[pmask][i] + matrix[i][j];
								parent[mask][j] = i;
							}
						}
					}
				}
			}
		}
		vector<int> ansindex(n);
		int p = 0;
		int p2;
		int valueans = (1 << n) - 1;
		for (int i = 1; i < n; i++) {
			if (dp[valueans][p] < dp[valueans][i]) {
				p = i;
			}
		}
		int mask = valueans;
		int t = n;
		while (p != -1) {
			ansindex[--t] = p;
			p2 = parent[mask][p];
			mask ^= 1 << p;
			p = p2;
		}

		string ans= A[ansindex[0]];
		int ii = ansindex[0];
		for (int i = 1; i < n; i++) {
			int j = ansindex[i];
			ans.append(A[j].substr(matrix[ii][j], A[j].length() - matrix[ii][j]));
			ii = j;
		}
 		return ans;
	}
};