题目描述
给你一个下标从 0 开始的数组 words
,它包含 n
个字符串。
定义 连接 操作 join(x, y)
表示将字符串 x
和 y
连在一起,得到 xy
。如果 x
的最后一个字符与 y
的第一个字符相等,连接后两个字符中的一个会被 删除。
比方说 join("ab", "ba") = "aba"
,join("ab", "cde") = "abcde"
。
你需要执行 n - 1
次 连接 操作。令 str_0 = words[0]
,从 i = 1
直到 i = n - 1
,对于第 i
个操作,你可以执行以下操作之一:
- 令
str_i = join(str_i - 1, words[i])
- 令
str_i = join(words[i], str_i - 1)
你的任务是使 str_n - 1
的长度 最小。
请你返回一个整数,表示 str_n - 1
的最小长度。
样例
输入:words = ["aa","ab","bc"]
输出:4
解释:这个例子中,我们按以下顺序执行连接操作,得到 str_2 的最小长度:
str0 = "aa"
str1 = join(str0, "ab") = "aab"
str2 = join(str1, "bc") = "aabc"
str2 的最小长度为 4。
输入:words = ["ab","b"]
输出:2
解释:这个例子中,str0 = "ab",可以得到两个不同的 str1:
join(str0, "b") = "ab" 或者 join("b", str0) = "bab"。
第一个字符串 "ab" 的长度最短,所以答案为 2。
输入:words = ["aaa","c","aba"]
输出:6
解释:这个例子中,我们按以下顺序执行连接操作,得到 str_2 的最小长度:
str0 = "aaa"
str1 = join(str0, "c") = "aaac"
str2 = join("aba", str1) = "abaaac"
str2 的最小长度为 6。
限制
1 <= words.length <= 1000
1 <= words[i].length <= 50
words[i]
中只包含小写英文字母。
算法
(动态规划) $O(n \Sigma^2)$
- 设状态 $f(i, j, k)$ 表示组装了前 $i$ 个字符串,且开头字符为 $j$,结尾字符为 $k$ 时的最小长度。
- 初始时,$f(0, w[0].front, w[0].back) = w[0].size$,其余为正无穷。
- 转移时,枚举 $j$ 和 $k$,并将当前字符串尝试拼接到开头或者拼接到结尾,根据 $j, k$ 与当前字符串的头尾字符的情况计算新的长度,并更新状态。
- 最终答案为 $\min(f(n, j, k))$。
- 可以使用滚动数组优化第一维的状态表示。
时间复杂度
- 状态数为 $O(n \Sigma^2)$,转移时间为常数,故时间复杂度为 $O(n \Sigma^2)$。
空间复杂度
- 使用滚动数组,空间复杂度为 $O(\Sigma^2)$。
C++ 代码
const int N = 26;
class Solution {
public:
int minimizeConcatenatedLength(vector<string>& words) {
const int n = words.size();
int f[N][N], g[N][N];
memset(f, 0x3f, sizeof(f));
memset(g, 0x3f, sizeof(g));
f[words[0].front() - 'a'][words[0].back() - 'a'] = words[0].size();
for (int i = 1; i < n; i++) {
int len = words[i].size();
int s = words[i].front() - 'a';
int e = words[i].back() - 'a';
for (int j = 0; j < 26; j++)
for (int k = 0; k < 26; k++) {
g[j][e] = min(g[j][e], f[j][k] + len - (s == k));
g[s][k] = min(g[s][k], f[j][k] + len - (e == j));
}
memcpy(f, g, sizeof(f));
memset(g, 0x3f, sizeof(g));
}
int ans = INT_MAX;
for (int j = 0; j < 26; j++)
for (int k = 0; k < 26; k++)
ans = min(ans, f[j][k]);
return ans;
}
};