2746-字符串连接删减字母

给你一个下标从 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 <= 1000
1 <= words[i].length <= 50
words[i] 中只包含小写英文字母。

解法：DP

因为每次操作我们只关心 str 的第一个以及最后一个字符，因此维护 f(i, j, k) 表示已经连接了前 i 个字符串，此时 str 的第一个字符是 j，最后一个字符是 k 的最小长度。设第 i 个字符串长度为 l_i，第一个字符为 x_i，最后一个字符为 y_i。我们可以枚举把它接在开头还是末尾，以及原来开头/末尾的字符是哪个。

如果接在开头，则

f(i, x_i, k) = \min\begin{cases}
f(i - 1, y_i, k) + l_i - 1 & \
f(i - 1, j, k) + l_i & j \ne y_i
\end{cases}

如果接在末尾，则

f(i, j, y_i) = \min\begin{cases}
f(i - 1, j, x_i) + l_i - 1 & \
f(i - 1, j, k) + l_i & k \ne x_i
\end{cases}

初值 f(1, x_i, y_i) = l_i，答案就是 \min (f(n, j, k))。复杂度 \mathcal{O}(n|\Sigma|^2)，其中 |\Sigma| 表示字母表大小。

参考代码（c++）

class Solution {
public:
    int minimizeConcatenatedLength(vector<string>& words) {
        int n = words.size();

        const int INF = 1e9;
        int f[n][26][26];
        for (int i = 0; i < n; i++) for (int j = 0; j < 26; j++) for (int k = 0; k < 26; k++) f[i][j][k] = INF;
        f[0][words[0][0] - 'a'][words[0].back() - 'a'] = words[0].size();

        for (int i = 1; i < n; i++) {
            int len = words[i].size(), x = words[i][0] - 'a', y = words[i].back() - 'a';
            for (int j = 0; j < 26; j++) for (int k = 0; k < 26; k++) {
                if (y == j) f[i][x][k] = min(f[i][x][k], f[i - 1][j][k] + len - 1);
                else f[i][x][k] = min(f[i][x][k], f[i - 1][j][k] + len);
                if (x == k) f[i][j][y] = min(f[i][j][y], f[i - 1][j][k] + len - 1);
                else f[i][j][y] = min(f[i][j][y], f[i - 1][j][k] + len);
            }
        }

        int ans = INF;
        for (int j = 0; j < 26; j++) for (int k = 0; k < 26; k++) ans = min(ans, f[n - 1][j][k]);
        return ans;
    }
};