class Solution {
public:
int minimizeConcatenatedLength(vector<string>& words) {
}
};
6898. 字符串连接删减字母
给你一个下标从 0 开始的数组 words ，它包含 n 个字符串。
定义 连接 操作 join(x, y) 表示将字符串 x 和 y 连在一起，得到 xy 。如果 x 的最后一个字符与 y 的第一个字符相等，连接后两个字符中的一个会被 删除 。
比方说 join("ab", "ba") = "aba" ， join("ab", "cde") = "abcde" 。
你需要执行 n - 1 次 连接 操作。令 str0 = words[0] ，从 i = 1 直到 i = n - 1 ，对于第 i 个操作，你可以执行以下操作之一：
stri = join(stri - 1, words[i])stri = join(words[i], stri - 1)你的任务是使 strn - 1 的长度 最小 。
请你返回一个整数，表示 strn - 1 的最小长度。
示例 1：
输入：words = ["aa","ab","bc"] 输出：4 解释：这个例子中，我们按以下顺序执行连接操作，得到str2的最小长度：str0 = "aa"str1 = join(str0, "ab") = "aab"str2 = join(str1, "bc") = "aabc"str2的最小长度为 4 。
示例 2：
输入：words = ["ab","b"]
输出：2
解释：这个例子中，str0 = "ab"，可以得到两个不同的 str1：
join(str0, "b") = "ab" 或者 join("b", str0) = "bab" 。
第一个字符串 "ab" 的长度最短，所以答案为 2 。
示例 3：
输入：words = ["aaa","c","aba"] 输出：6 解释：这个例子中，我们按以下顺序执行连接操作，得到str2 的最小长度：str0 = "aaa"str1 = join(str0, "c") = "aaac"str2 = join("aba", str1) = "abaaac"str2的最小长度为 6 。
提示：
1 <= words.length <= 10001 <= words[i].length <= 50words[i] 中只包含小写英文字母。原站题解
java 解法, 执行用时: 52 ms, 内存消耗: 42.8 MB, 提交时间: 2023-06-25 09:43:33
class Solution {
public int minimizeConcatenatedLength(String[] words) {
int inf = Integer.MAX_VALUE;
int[][] cnt = new int[26][26];
for (int i = 0; i < 26; i++) Arrays.fill(cnt[i], inf);
// cnt[i][j]表示第一个字符为 i,最后一个字符为 j 的最短长度。
cnt[words[0].charAt(0)-'a'][words[0].charAt(words[0].length()-1)-'a'] = words[0].length();
for (int i = 1; i < words.length; i++) {
String str = words[i];
int[][] tmp = new int[26][26];
for (int l = 0; l < 26; l++) Arrays.fill(tmp[l], inf);
int l = str.charAt(0)-'a', r = str.charAt(str.length()-1)-'a';
for (int j = 0; j < 26; j++) {
for (int k = 0; k < 26; k++) {
if (cnt[j][k] != inf) {
int len = cnt[j][k]+str.length();
if (j == r) tmp[l][k] = Math.min(tmp[l][k], len-1);
else tmp[l][k] = Math.min(tmp[l][k], len);
if (k == l) tmp[j][r] = Math.min(tmp[j][r] , len-1);
else tmp[j][r] = Math.min(tmp[j][r] , len);
}
}
}
cnt = tmp;
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
if (cnt[i][j] > 0) {
res = Math.min(res, cnt[i][j]);
}
}
}
return res;
}
}
golang 解法, 执行用时: 76 ms, 内存消耗: 13.5 MB, 提交时间: 2023-06-25 09:42:20
// 动态规划
// dp[i][j][k]，表示，从0到i的word，组成的以j开头、以k结尾的str，的最短长度
func minimizeConcatenatedLength(words []string) int {
n := len(words)
dp := make([][26][26]int, n)
for i := range dp {
for j := range dp[i] {
for k := range dp[i][j] {
dp[i][j][k] = math.MaxInt32
}
}
}
dp[0][words[0][0]-'a'][words[0][len(words[0])-1]-'a'] = len(words[0])
for i := 1; i < n; i++ {
si := int(words[i][0] - 'a')
ei := int(words[i][len(words[i])-1] - 'a')
l := len(words[i])
for j := 0; j < 26; j++ {
for k := 0; k < 26; k++ {
if dp[i-1][j][k] == -1 {
continue
}
if ei == j {
dp[i][si][k] = min(dp[i][si][k], dp[i-1][j][k]+l-1)
} else {
dp[i][si][k] = min(dp[i][si][k], dp[i-1][j][k]+l)
}
if k == si {
dp[i][j][ei] = min(dp[i][j][ei], dp[i-1][j][k]+l-1)
} else {
dp[i][j][ei] = min(dp[i][j][ei], dp[i-1][j][k]+l)
}
}
}
}
res := math.MaxInt32
for i := range dp[n-1] {
for _, d := range dp[n-1][i] {
res = min(res, d)
}
}
return res
}
func min(a, b int) int { if a < b { return a }; return b }
python3 解法, 执行用时: 388 ms, 内存消耗: 52.5 MB, 提交时间: 2023-06-25 09:40:18
'''
记忆化搜索
dfs(i, s, e): 第 i 次操作，前面字符串开头为 s，末尾为e形成的最短长度
'''
class Solution:
def minimizeConcatenatedLength(self, words: List[str]) -> int:
@cache
def dfs(i: int, s: str, e: str) -> int:
if i == n:
return 0
string = words[i]
res = dfs(i + 1, s, string[-1]) + len(string) - int(string[0] == e)
res = min(res, dfs(i + 1,string[0], e) + len(string) - int(string[-1] == s))
return res
n = len(words)
return dfs(1, words[0][0], words[0][-1]) + len(words[0])