跳转至

2746. 字符串连接删减字母

来源第 107 场双周赛 Q3难度中等分数2126

题目描述

给你一个下标从 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] 中只包含小写英文字母。

解法

方法一：记忆化搜索

思考

按给定顺序把单词接到当前串的左端或右端，相邻端点相同则删一个字符，求最短终长。每步两种选择，深度为 \(n\le 1000\)，裸搜索不可行。

终长只依赖已接串的首尾字符。 \(dfs(i,a,b)\) 表示从第 \(i\) 个词起、当前首尾为 \(a,b\) 时还需付出的最小长度；接到右侧比较 \(s[0]\) 与 \(b\)，接到左侧比较 \(s[-1]\) 与 \(a\)。记忆化后状态为 \(O(n\cdot 26^2)\)。

我们注意到，字符串连接时，字符串的第一个字符和最后一个字符会影响到连接后字符串的长度。因此，我们设计一个函数 \(dfs(i, a, b)\)，表示从第 \(i\) 个字符串开始连接，且此前已经连接的字符串的第一个字符为 \(a\)，最后一个字符为 \(b\) 时，连接后字符串的最小长度。

函数 \(dfs(i, a, b)\) 的执行过程如下：

  • 如果 \(i = n\)，说明所有字符串已经连接完毕，返回 \(0\)；
  • 否则，我们考虑将第 \(i\) 个字符串连接到已经连接的字符串的末尾或者开头，得到连接后字符串的长度 \(x\) 和 \(y\)，则 \(dfs(i, a, b) = \min(x, y) + |words[i]|\)。

为了避免重复计算，我们使用记忆化搜索的方法。具体地，我们使用一个三维数组 \(f\) 存储所有的 \(dfs(i, a, b)\) 的返回值。当我们需要计算 \(dfs(i, a, b)\) 时，如果 \(f[i][a][b]\) 已经被计算过，我们直接返回 \(f[i][a][b]\)；否则我们按照上述的递推关系计算 \(dfs(i, a, b)\) 的值，并将其存入 \(f[i][a][b]\) 中。

在主函数中，我们直接返回 \(|words[0]| + dfs(1, words[0][0], words[0][|words[0]| - 1])\)。

时间复杂度 \(O(n \times C^2)\)，空间复杂度 \(O(n \times C^2)\)，其中 \(C\) 表示字符串的最大长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def minimizeConcatenatedLength(self, words: List[str]) -> int:
        @cache
        def dfs(i: int, a: str, b: str) -> int:
            if i >= len(words):
                return 0
            s = words[i]
            x = dfs(i + 1, a, s[-1]) - int(s[0] == b)
            y = dfs(i + 1, s[0], b) - int(s[-1] == a)
            return len(s) + min(x, y)

        return len(words[0]) + dfs(1, words[0][0], words[0][-1])

 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
class Solution {
    private Integer[][][] f;
    private String[] words;
    private int n;

    public int minimizeConcatenatedLength(String[] words) {
        n = words.length;
        this.words = words;
        f = new Integer[n][26][26];
        return words[0].length()
            + dfs(1, words[0].charAt(0) - 'a', words[0].charAt(words[0].length() - 1) - 'a');
    }

    private int dfs(int i, int a, int b) {
        if (i >= n) {
            return 0;
        }
        if (f[i][a][b] != null) {
            return f[i][a][b];
        }
        String s = words[i];
        int m = s.length();
        int x = dfs(i + 1, a, s.charAt(m - 1) - 'a') - (s.charAt(0) - 'a' == b ? 1 : 0);
        int y = dfs(i + 1, s.charAt(0) - 'a', b) - (s.charAt(m - 1) - 'a' == a ? 1 : 0);
        return f[i][a][b] = m + Math.min(x, y);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minimizeConcatenatedLength(vector<string>& words) {
        int n = words.size();
        int f[n][26][26];
        memset(f, 0, sizeof(f));
        function<int(int, int, int)> dfs = [&](int i, int a, int b) {
            if (i >= n) {
                return 0;
            }
            if (f[i][a][b]) {
                return f[i][a][b];
            }
            auto s = words[i];
            int m = s.size();
            int x = dfs(i + 1, a, s[m - 1] - 'a') - (s[0] - 'a' == b);
            int y = dfs(i + 1, s[0] - 'a', b) - (s[m - 1] - 'a' == a);
            return f[i][a][b] = m + min(x, y);
        };
        return words[0].size() + dfs(1, words[0].front() - 'a', words[0].back() - 'a');
    }
};

 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
func minimizeConcatenatedLength(words []string) int {
    n := len(words)
    f := make([][26][26]int, n)
    var dfs func(i, a, b int) int
    dfs = func(i, a, b int) int {
        if i >= n {
            return 0
        }
        if f[i][a][b] > 0 {
            return f[i][a][b]
        }
        s := words[i]
        m := len(s)
        x := dfs(i+1, a, int(s[m-1]-'a'))
        y := dfs(i+1, int(s[0]-'a'), b)
        if int(s[0]-'a') == b {
            x--
        }
        if int(s[m-1]-'a') == a {
            y--
        }
        f[i][a][b] = m + min(x, y)
        return f[i][a][b]
    }
    return len(words[0]) + dfs(1, int(words[0][0]-'a'), int(words[0][len(words[0])-1]-'a'))
}

 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
function minimizeConcatenatedLength(words: string[]): number {
    const n = words.length;
    const f: number[][][] = Array(n)
        .fill(0)
        .map(() =>
            Array(26)
                .fill(0)
                .map(() => Array(26).fill(0)),
        );
    const dfs = (i: number, a: number, b: number): number => {
        if (i >= n) {
            return 0;
        }
        if (f[i][a][b] > 0) {
            return f[i][a][b];
        }
        const s = words[i];
        const m = s.length;
        const x =
            dfs(i + 1, a, s[m - 1].charCodeAt(0) - 97) - (s[0].charCodeAt(0) - 97 === b ? 1 : 0);
        const y =
            dfs(i + 1, s[0].charCodeAt(0) - 97, b) - (s[m - 1].charCodeAt(0) - 97 === a ? 1 : 0);
        return (f[i][a][b] = Math.min(x + m, y + m));
    };
    return (
        words[0].length +
        dfs(1, words[0][0].charCodeAt(0) - 97, words[0][words[0].length - 1].charCodeAt(0) - 97)
    );
}

方法二：动态规划

思考

每个词只能接到当前串的左端或右端，相邻字母相同就少记一个字符。单词个数可以到 \(1000\)，而先尝试接到右端时下标总是加一，递归深度就是 \(n\)。已经接好的串对后面的影响只剩首尾两个字母。于是令 \(f[i][a][b]\) 为从第 \(i\) 个词起、当前首尾为 \(a,b\) 时还要增加的最短长度， \(f[n]\) 为 \(0\)，再按 \(i\) 从大到小、枚举全部首尾填写。

设 \(f[i][a][b]\) 表示从第 \(i\) 个单词开始连接，且此前字符串的首字符为 \(a\)、尾字符为 \(b\) 时，还能增加的最短长度。边界 \(f[n][a][b]=0\)。从 \(i=n-1\) 递减到 \(1\)，对每个首尾 \(a,b\) 考虑两种接法：把 \(words[i]\) 接到右侧时，若它的首字符等于 \(b\) 则少一个字符，新的尾字符是它的末字符；接到左侧时，若它的末字符等于 \(a\) 则少一个字符，新的首字符是它的首字符。 \(f[i][a][b]\) 取两种接法中较短的那个，再加上 \(|words[i]|\)。答案为 \(|words[0]| + f[1][words[0][0]][words[0][|words[0]|-1]]\)。

时间复杂度 \(O(n \times |\Sigma|^2)\)，空间复杂度 \(O(n \times |\Sigma|^2)\)。其中 \(n\) 为单词个数， \(|\Sigma|\) 为字符集大小，本题中 \(|\Sigma| = 26\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def minimizeConcatenatedLength(self, words: List[str]) -> int:
        n = len(words)
        f = [[[0] * 26 for _ in range(26)] for _ in range(n + 1)]
        for i in range(n - 1, 0, -1):
            s = words[i]
            m = len(s)
            c, d = ord(s[0]) - 97, ord(s[-1]) - 97
            for a in range(26):
                for b in range(26):
                    x = f[i + 1][a][d] - (c == b)
                    y = f[i + 1][c][b] - (d == a)
                    f[i][a][b] = m + min(x, y)
        a, b = ord(words[0][0]) - 97, ord(words[0][-1]) - 97
        return len(words[0]) + f[1][a][b]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minimizeConcatenatedLength(String[] words) {
        int n = words.length;
        int[][][] f = new int[n + 1][26][26];
        for (int i = n - 1; i > 0; --i) {
            String s = words[i];
            int m = s.length();
            int c = s.charAt(0) - 'a';
            int d = s.charAt(m - 1) - 'a';
            for (int a = 0; a < 26; ++a) {
                for (int b = 0; b < 26; ++b) {
                    int x = f[i + 1][a][d] - (c == b ? 1 : 0);
                    int y = f[i + 1][c][b] - (d == a ? 1 : 0);
                    f[i][a][b] = m + Math.min(x, y);
                }
            }
        }
        int a = words[0].charAt(0) - 'a';
        int b = words[0].charAt(words[0].length() - 1) - 'a';
        return words[0].length() + f[1][a][b];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minimizeConcatenatedLength(vector<string>& words) {
        int n = words.size();
        vector<vector<vector<int>>> f(n + 1, vector<vector<int>>(26, vector<int>(26)));
        for (int i = n - 1; i > 0; --i) {
            auto& s = words[i];
            int m = s.size();
            int c = s[0] - 'a';
            int d = s[m - 1] - 'a';
            for (int a = 0; a < 26; ++a) {
                for (int b = 0; b < 26; ++b) {
                    int x = f[i + 1][a][d] - (c == b);
                    int y = f[i + 1][c][b] - (d == a);
                    f[i][a][b] = m + min(x, y);
                }
            }
        }
        int a = words[0].front() - 'a';
        int b = words[0].back() - 'a';
        return words[0].size() + f[1][a][b];
    }
};

 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
func minimizeConcatenatedLength(words []string) int {
    n := len(words)
    f := make([][26][26]int, n+1)
    for i := n - 1; i > 0; i-- {
        s := words[i]
        m := len(s)
        c := int(s[0] - 'a')
        d := int(s[m-1] - 'a')
        for a := 0; a < 26; a++ {
            for b := 0; b < 26; b++ {
                x := f[i+1][a][d]
                y := f[i+1][c][b]
                if c == b {
                    x--
                }
                if d == a {
                    y--
                }
                f[i][a][b] = m + min(x, y)
            }
        }
    }
    a := int(words[0][0] - 'a')
    b := int(words[0][len(words[0])-1] - 'a')
    return len(words[0]) + f[1][a][b]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function minimizeConcatenatedLength(words: string[]): number {
    const n = words.length;
    const f: number[][][] = Array.from({ length: n + 1 }, () =>
        Array.from({ length: 26 }, () => Array(26).fill(0)),
    );
    for (let i = n - 1; i > 0; --i) {
        const s = words[i];
        const m = s.length;
        const c = s.charCodeAt(0) - 97;
        const d = s.charCodeAt(m - 1) - 97;
        for (let a = 0; a < 26; ++a) {
            for (let b = 0; b < 26; ++b) {
                const x = f[i + 1][a][d] - (c === b ? 1 : 0);
                const y = f[i + 1][c][b] - (d === a ? 1 : 0);
                f[i][a][b] = m + Math.min(x, y);
            }
        }
    }
    const a = words[0].charCodeAt(0) - 97;
    const b = words[0].charCodeAt(words[0].length - 1) - 97;
    return words[0].length + f[1][a][b];
}

评论