LeetCode 2746. Decremental String Concatenation Solution in Java, C++, Python & More | Explanation + Code

Description

You are given a 0-indexed array words containing n strings.

Let's define a join operation join(x, y) between two strings x and y as concatenating them into xy. However, if the last character of x is equal to the first character of y, one of them is deleted.

For example join("ab", "ba") = "aba" and join("ab", "cde") = "abcde".

You are to perform n - 1 join operations. Let str0 = words[0]. Starting from i = 1 up to i = n - 1, for the ith operation, you can do one of the following:

• Make stri = join(stri - 1, words[i])
• Make stri = join(words[i], stri - 1)

Your task is to minimize the length of strn - 1.

Return an integer denoting the minimum possible length of strn - 1.

 

Example 1:

Input: words = ["aa","ab","bc"]
Output: 4
Explanation: In this example, we can perform join operations in the following order to minimize the length of str2: 
str0 = "aa"
str1 = join(str0, "ab") = "aab"
str2 = join(str1, "bc") = "aabc" 
It can be shown that the minimum possible length of str2 is 4.

Example 2:

Input: words = ["ab","b"]
Output: 2
Explanation: In this example, str0 = "ab", there are two ways to get str1: 
join(str0, "b") = "ab" or join("b", str0) = "bab". 
The first string, "ab", has the minimum length. Hence, the answer is 2.

Example 3:

Input: words = ["aaa","c","aba"]
Output: 6
Explanation: In this example, we can perform join operations in the following order to minimize the length of str2: 
str0 = "aaa"
str1 = join(str0, "c") = "aaac"
str2 = join("aba", str1) = "abaaac"
It can be shown that the minimum possible length of str2 is 6.

 

 

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 50
• Each character in words[i] is an English lowercase letter

Solutions

Solution 1: Memoization Search

We notice that when concatenating strings, the first and last characters of the string will affect the length of the concatenated string. Therefore, we design a function dfs(i, a, b), which represents the minimum length of the concatenated string starting from the i-th string, and the first character of the previously concatenated string is a, and the last character is b.

The execution process of the function dfs(i, a, b) is as follows:

• If i = n, it means that all strings have been concatenated, return 0;
• Otherwise, we consider concatenating the i-th string to the end or the beginning of the already concatenated string, and get the lengths x and y of the concatenated string, then dfs(i, a, b) = min(x, y) + |words[i]|.

To avoid repeated calculations, we use the method of memoization search. Specifically, we use a three-dimensional array f to store all the return values of dfs(i, a, b). When we need to calculate dfs(i, a, b), if f[i][a][b] has been calculated, we directly return f[i][a][b]; otherwise, we calculate the value of dfs(i, a, b) according to the above recurrence relation, and store it in f[i][a][b].

In the main function, we directly return |words[0]| + dfs(1, words[0][0], words[0][|words[0]| - 1]).

The time complexity is O(n × C²), and the space complexity is O(n × C²). Where C represents the maximum length of the string.

PythonJavaC++GoTypeScript

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])(code-box)

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); } }(code-box)

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'); } };(code-box)

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')) }(code-box)

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) ); }(code-box)