Leetcode Problem 2746. Decremental String Concatenation

2746. Decremental String Concatenation

Leetcode Solutions

Dynamic Programming withD Memoization

  1. Initialize a 3D array dp with dimensions [n][26][26] to store the minimum length for each state, where n is the number of words, and 26 represents all possible lowercase English letters.
  2. Set all values in dp to a large number (e.g., Integer.MAX_VALUE) to represent uncomputed states.
  3. Define the base case: dp[0][first][last] is the length of the first word, where first and last are the indices of the first and last characters of the first word.
  4. Iterate over all words from index 1 to n-1.
  5. For each word, compute the minimum length for both possibilities of joining (before and after) and update the dp array accordingly.
  6. After processing all words, find the minimum length from the last layer of the dp array.
  7. Return the minimum length as the result.
UML Thumbnail

Greedy Approach with Sorting

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...