Medium

题目描述

给你一个下标从 0 开始的数组 words，包含 n 个字符串。

定义两个字符串 x 和 y 之间的连接操作 join(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] 中的每个字符都是英文小写字母

解题思路

这是一道经典的动态规划问题，关键在于识别状态的特征。

核心观察： 字符串连接的长度只取决于当前字符串的首尾字符，以及要连接的字符串的首尾字符。如果两个字符串连接时首尾字符相同，长度会减少1。

状态定义： 使用三维动态规划 dp[i][first][last] 表示处理前 i 个单词，得到的字符串以字符 first 开头、以字符 last 结尾时的最小长度。

状态转移： 对于第 i 个单词 words[i]，我们有两种连接方式：

  1. 将 words[i] 放在当前字符串之后：join(current, words[i])
  2. 将 words[i] 放在当前字符串之前：join(words[i], current)

每种连接方式都需要检查是否有字符重叠可以删除。

算法流程：

  1. 初始化：第一个单词的状态
  2. 逐个处理后续单词，尝试两种连接方式
  3. 更新所有可能的状态组合
  4. 返回最终所有状态中的最小长度

时间复杂度为 O(n × 26²)，其中 n 是单词数量，26² 表示所有可能的首尾字符组合。

代码实现

class Solution {
public:
    int minimizeConcatenatedLength(vector<string>& words) {
        int n = words.size();
        // dp[i][first][last] = minimum length ending at word i with first and last chars
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(26, vector<int>(26, INT_MAX)));
        
        // Initialize with first word
        char firstChar = words[0][0];
        char lastChar = words[0].back();
        dp[0][firstChar - 'a'][lastChar - 'a'] = words[0].length();
        
        for (int i = 1; i < n; i++) {
            char currFirst = words[i][0];
            char currLast = words[i].back();
            int currLen = words[i].length();
            
            for (int first = 0; first < 26; first++) {
                for (int last = 0; last < 26; last++) {
                    if (dp[i-1][first][last] == INT_MAX) continue;
                    
                    // Option 1: join(prev, curr)
                    int newLen1 = dp[i-1][first][last] + currLen;
                    if (last == (currFirst - 'a')) newLen1--; // overlap
                    dp[i][first][currLast - 'a'] = min(dp[i][first][currLast - 'a'], newLen1);
                    
                    // Option 2: join(curr, prev)
                    int newLen2 = dp[i-1][first][last] + currLen;
                    if ((currLast - 'a') == first) newLen2--; // overlap
                    dp[i][currFirst - 'a'][last] = min(dp[i][currFirst - 'a'][last], newLen2);
                }
            }
        }
        
        int result = INT_MAX;
        for (int first = 0; first < 26; first++) {
            for (int last = 0; last < 26; last++) {
                result = min(result, dp[n-1][first][last]);
            }
        }
        
        return result;
    }
};

class Solution:
    def minimizeConcatenatedLength(self, words: List[str]) -> int:
        n = len(words)
        # dp[i][first][last] = minimum length ending at word i with first and last chars
        dp = [[[float('inf')] * 26 for _ in range(26)] for _ in range(n)]
        
        # Initialize with first word
        first_char = ord(words[0][0]) - ord('a')
        last_char = ord(words[0][-1]) - ord('a')
        dp[0][first_char][last_char] = len(words[0])
        
        for i in range(1, n):
            curr_first = ord(words[i][0]) - ord('a')
            curr_last = ord(words[i][-1]) - ord('a')
            curr_len = len(words[i])
            
            for first in range(26):
                for last in range(26):
                    if dp[i-1][first][last] == float('inf'):
                        continue
                    
                    # Option 1: join(prev, curr)
                    new_len1 = dp[i-1][first][last] + curr_len
                    if last == curr_first:
                        new_len1 -= 1  # overlap
                    dp[i][first][curr_last] = min(dp[i][first][curr_last], new_len1)
                    
                    # Option 2: join(curr, prev)
                    new_len2 = dp[i-1][first][last] + curr_len
                    if curr_last == first:
                        new_len2 -= 1  # overlap
                    dp[i][curr_first][last] = min(dp[i][curr_first][last], new_len2)
        
        result = float('inf')
        for first in range(26):
            for last in range(26):
                result = min(result, dp[n-1][first][last])
        
        return result

public class Solution {
    public int MinimizeConcatenatedLength(string[] words) {
        int n = words.Length;
        // dp[i][first][last] = minimum length ending at word i with first and last chars
        int[,,] dp = new int[n, 26, 26];
        
        // Initialize with max values
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 26; j++) {
                for (int k = 0; k < 26; k++) {
                    dp[i, j, k] = int.MaxValue;
                }
            }
        }
        
        // Initialize with first word
        int firstChar = words[0][0] - 'a';
        int lastChar = words[0][words[0].Length - 1] - 'a';
        dp[0, firstChar, lastChar] = words[0].Length;
        
        for (int i = 1; i < n; i++) {
            int currFirst = words[i][0] - 'a';
            int currLast = words[i][words[i].Length - 1] - 'a';
            int currLen = words[i].Length;
            
            for (int first = 0; first < 26; first++) {
                for (int last = 0; last < 26; last++) {
                    if (dp[i-1, first, last] == int.MaxValue) continue;
                    
                    // Option 1: join(prev, curr)
                    int newLen1 = dp[i-1, first, last] + currLen;
                    if (last == currFirst) newLen1--; // overlap
                    dp[i, first, currLast] = Math.Min(dp[i, first, currLast], newLen1);
                    
                    // Option 2: join(curr, prev)
                    int newLen2 = dp[i-1, first, last] + currLen;
                    if (currLast == first) newLen2--; // overlap
                    dp[i, currFirst, last] = Math.Min(dp[i, currFirst, last], newLen2);
                }
            }
        }
        
        int result = int.MaxValue;
        for (int first = 0; first < 26; first++) {
            for (int last = 0; last < 26; last++) {
                result = Math.Min(result, dp[n-1, first, last]);
            }
        }
        
        return result;
    }
}

var minimizeConcatenatedLength = function(words) {
    const n = words.length;
    if (n === 1) return words[0].length;
    
    const memo = new Map();
    
    function dp(index, firstChar, lastChar) {
        if (index === n) return 0;
        
        const key = `${index}-${firstChar}-${lastChar}`;
        if (memo.has(key)) return memo.get(key);
        
        const word = words[index];
        const wordFirst = word[0];
        const wordLast = word[word.length - 1];
        const wordLen = word.length;
        
        // Option 1: current + word (current string + new word)
        let len1 = wordLen;
        if (lastChar === wordFirst) len1--;
        len1 += dp(index + 1, firstChar, wordLast);
        
        // Option 2: word + current (new word + current string)
        let len2 = wordLen;
        if (wordLast === firstChar) len2--;
        len2 += dp(index + 1, wordFirst, lastChar);
        
        const result = Math.min(len1, len2);
        memo.set(key, result);
        return result;
    }
    
    const firstWord = words[0];
    return firstWord.length + dp(1, firstWord[0], firstWord[firstWord.length - 1]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n × 26²)
空间复杂度O(n × 26²)

其中 n 是单词数量，26² 表示所有可能的首尾字符组合。空间复杂度可以优化为 O(26²)，因为只需要保存前一层的状态。

相关题目