Skip to content

2746. Decremental String Concatenation 👍

  • Time: $O(n \cdot 26^2) = O(n)$
  • Space: $O(n \cdot 26^2) = O(n)$
 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
30
31
32
33
34
class Solution {
 public:
  int minimizeConcatenatedLength(vector<string>& words) {
    vector<vector<vector<int>>> mem(words.size(),
                                    vector<vector<int>>(26, vector<int>(26)));
    return words[0].length() + minimizeConcatenatedLength(words, 1,
                                                          words[0].front(),
                                                          words[0].back(), mem);
  }

 private:
  // Returns the minimum concatenated length of the first i words starting with
  // `first` and ending in `last`.
  int minimizeConcatenatedLength(const vector<string>& words, int i, char first,
                                 char last, vector<vector<vector<int>>>& mem) {
    if (i == words.size())
      return 0;
    const int j = first - 'a';
    const int k = last - 'a';
    if (mem[i][j][k] > 0)
      return mem[i][j][k];
    const char nextFirst = words[i].front();
    const char nextLast = words[i].back();
    return mem[i][j][k] =  //
           words[i].length() +
           min(
               // join(words[i - 1], words[i])
               minimizeConcatenatedLength(words, i + 1, first, nextLast, mem) -
                   (last == nextFirst ? 1 : 0),
               // join(words[i], words[i - 1])
               minimizeConcatenatedLength(words, i + 1, nextFirst, last, mem) -
                   (first == nextLast ? 1 : 0));
  }
};

 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
class Solution {
  public int minimizeConcatenatedLength(String[] words) {
    int[][][] mem = new int[words.length][26][26];
    return words[0].length() + minimizeConcatenatedLength(words, 1, words[0].charAt(0),
                                                          words[0].charAt(words[0].length() - 1),
                                                          mem);
  }

  private int minimizeConcatenatedLength(String[] words, int i, char first, char last,
                                         int[][][] mem) {
    if (i == words.length)
      return 0;
    final int j = first - 'a';
    final int k = last - 'a';
    if (mem[i][j][k] > 0)
      return mem[i][j][k];
    final char nextFirst = words[i].charAt(0);
    final char nextLast = words[i].charAt(words[i].length() - 1);
    return mem[i][j][k] =   //
        words[i].length() + //
        Math.min(
            // join(words[i - 1], words[i])
            minimizeConcatenatedLength(words, i + 1, first, nextLast, mem) -
                (last == nextFirst ? 1 : 0),
            // join(words[i], words[i - 1])
            minimizeConcatenatedLength(words, i + 1, nextFirst, last, mem) -
                (first == nextLast ? 1 : 0));
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def minimizeConcatenatedLength(self, words: List[str]) -> int:
    @functools.lru_cache(None)
    def dp(i: int, first: str, last: str) -> int:
      """
      Returns the minimum concatenated length of the first i words starting with
      `first` and ending in `last`.
      """
      if i == len(words):
        return 0
      nextFirst = words[i][0]
      nextLast = words[i][-1]
      return len(words[i]) + min(
          # join(words[i - 1], words[i])
          dp(i + 1, first, nextLast) - (last == nextFirst),
          # join(words[i], words[i - 1])
          dp(i + 1, nextFirst, last) - (first == nextLast)
      )

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